InterviewStreet Triplet optimization

Question

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 :)

Answer 1

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);
    }

}

Answer 2

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.