Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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(;
        int x=scn.nextInt();
        arr=new int[x];
        helper=new int[x];
        for(int i=0;i<x;i++)
        int triplets=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]))


If there is a way to optimize this solution or approach it differently, please let me know.

share|improve this question

migrated from Jan 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(;
        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[]>() {
            public int compare(int[] o1, int[] o2) {

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

                return result;

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

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


share|improve this answer
  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();


    int x = 100000;




     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

Your Answer


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.