Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I came up with a solution for the InterviewStreet problem "Triplet"

link to the problem

In short, there is an integer array d which does not contain more than two elements of the same value. How many distinct ascending triples (d[i] < d[j] < d[k], i < j < k) are present?

It successfully passes 9 test cases of 15. but my solution exceeds time limit in other test cases.

here is my solution in java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 *
 * @author Dumindu
 */
public class Triplets {
    public static void main(String args[])
    {
        int[] arr,helper;
        Scanner scn=new Scanner(System.in);
        int x=scn.nextInt();
        arr=new int[x];
        helper=new int[x];
        for(int i=0;i<x;i++)
        {
            arr[i]=scn.nextInt();
        }
        int triplets=0;
        helper[0]=0;
        Map<Integer,Integer> map1=new HashMap<Integer,Integer>();

        for(int i=0;i<x;i++)
        {
            int minVals=0;

            Set<Integer> set=new HashSet<Integer>();
            int tempTrip=0;
            for(int j=i-1;j>=0;j--)
            {   
                if(arr[j]<arr[i] && !set.contains(arr[j]))
                {
                    minVals++;
                    tempTrip+=helper[j];
                    set.add(arr[j]);
                }
            }
            helper[i]=minVals;
            if(!map1.containsKey(arr[i]))
            {
                triplets+=tempTrip;
                map1.put(arr[i],tempTrip);
            }
            else
            {
                triplets=triplets-map1.get(arr[i])+tempTrip;
            }
        }
        System.out.println(triplets);
    }

}

If there is a way to optimize this solution please let me know. If I should take another approach different than this please also let me know :)

share|improve this question

migrated from stackoverflow.com Jan 10 '13 at 23:05

This question came from our site for professional and enthusiast programmers.

1  
You didn't exactly go out of your way to help us understand your variable names. –  Marko Topolnik Jan 10 '13 at 11:36
add comment

2 Answers 2

I found it difficult to understand your solution, I wrote another solution that first creates all triplets may also maybe some duplicate ones. Then I sort the triplets so that duplicates are "together" and then I remove duplicates.

I would like to find an algorithm that does not create those duplicates so there would be no need to keep all triplets in memory, but I did not found a solution yet :(

Anyway here is what I did:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Solution {

    public static void main(String... args) {

        Scanner scanner = new Scanner(System.in);
        int elements = scanner.nextInt();
        int[] sequence = new int[elements];

        for (int i = 0; i < elements; i++) {
            sequence[i] = scanner.nextInt();
        }

//        sequence[0] = 1;
//        sequence[1] = 1;
//        sequence[2] = 2;
//        sequence[3] = 2;
//        sequence[4] = 3;
//        sequence[5] = 4;

        List<int[]> triplets = new ArrayList<>();
        for (int i = 0; i < elements; i++) {
            int first = sequence[i];
            for (int j = i; j < elements; j++) {
                int second = sequence[j];
                if (second > first) {
                    for (int k = j; k < elements; k++) {
                        int third = sequence[k];
                        if (third > second) {
                            triplets.add(new int[] { first, second, third });
                        }
                    }
                }
            }
        }

        Collections.sort(triplets, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {

                int index = 0;
                int result = 0;
                int length = Math.min(o1.length, o2.length);
                do {
                    result = Integer.compare(o1[index],o2[index]);
                } while (result == 0 && ++index < length);



                return result;
            }

            @Override
            public Comparator<int[]> reverse() {
                throw new UnsupportedOperationException();
            }

            @Override
            public Comparator<int[]> compose(Comparator<? super int[]> other) {
                throw new UnsupportedOperationException();
            }
        });

        int tripletsNb = 0;
        int[] currentTriplet = null;
        for (int[] t : triplets) {
            // count non-duplicate triplets
            if (!Arrays.equals(currentTriplet, t)) tripletsNb++;
            currentTriplet = t;
            // System.out.println(Arrays.toString(t));
        }

        System.out.println(tripletsNb);
    }

}
share|improve this answer
add comment
  1. The problem looks like it would have a solution of complexity O(n log n). Yours have O(n^2). UPDATE: It indeed has a O(n log n) solution. google "number of increasing subsequences".
  2. The site says input size can be 10^5. O(n^2) algorithm with hash look-ups, hash inserts, and virtual function calls in the inner loop will not finish in a few minutes.
  3. By replacing

    int x=scn.nextInt();
    

    with

    int x = 100000;
    

    and

        arr[i]=scn.nextInt();
    

    with

     arr[i] = i + 1;
    

    you can easily test how your program performs with large input.

  4. A quick order of magnitude analysis: An increasing sequence of ~10^5 elements will have ~(10^5)^3 increasing subsequences of length 3. Since 10^3 ~= 2^10, 10^15 ~= 2^50. 2^50 >> 2^31. So your triplets variable will overflow. It should be an long.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.