# InterviewStreet Triplet optimization

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

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.

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];
}
}
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 or approach it differently, please let me know.

-

## migrated from stackoverflow.comJan 10 '13 at 23:05

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

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

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

}

-
1. The problem looks like it would have a solution of complexity $O(n log n)$. Yours has $O(n^2)$. google "number of increasing subsequences".
2. The site says input size can be $10^5$. A $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.

-