interviewstreet Triplet challenge

Question

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?

Input format:

The first line contains an integer N denoting the number of elements in the array. This is followed by a single line containing N integers separated by a single space with no leading/trailing spaces

Output format:

A single integer that denotes the number of distinct ascending triples present in the array

Constraints:

N <= 10^5 Every value in the array is present at most twice Every value in the array is a 32-bit positive integer

Sample input:

6 
1 1 2 2 3 4

Sample output:

4

Explanation:

The distinct triplets are

(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)

Another test case:

Input:

10
1 1 5 4 3 6 6 5 9 10

Output:

28

I tried to solve using DP. But out of 15 test cases only 7 test cases passed. Please help solve this problem.

Answer 1

You should note that you only need to know the number of elements that are smaller/larger than a particular element to know how many triples it serves as the middle point for. Using this you can calculate the number of triples quite easily, the only remaining problem is to get rid of duplicates, but given that you are limited to at most 2 of the same element, this is trivial.

I solved using a Binary Index Tree http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees.

I also did a small write up, http://www.kesannmcclean.com/?p=223.

Answer 2

package com.jai;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;

public class Triplets {

    int[] lSmaller, rLarger, treeArray, dscArray, lFlags, rFlags;

    int size, count = 0;

    Triplets(int aSize, int[] inputArray) {
        size = aSize;
        lSmaller = new int[size];
        rLarger = new int[size];
        dscArray = new int[size];
        int[] tmpArray = Arrays.copyOf(inputArray, inputArray.length);
        Arrays.sort(tmpArray);
        HashMap<Integer, Integer> tmpMap = new HashMap<Integer, Integer>(size);
        for (int i = 0; i < size; i++) {
            if (!tmpMap.containsKey(tmpArray[i])) {
                count++;
                tmpMap.put(tmpArray[i], count);
            }
        }
        count++;
        treeArray = new int[count];
        lFlags = new int[count];
        rFlags = new int[count];
        for (int i = 0; i < size; i++) {
            dscArray[i] = tmpMap.get(inputArray[i]);
        }

    }

    void update(int idx) {
        while (idx < count) {
            treeArray[idx]++;

            idx += (idx & -idx);
        }
    }

    int read(int index) {
        int sum = 0;
        while (index > 0) {
            sum += treeArray[index];
            index -= (index & -index);
        }
        return sum;
    }

    void countLeftSmaller() {
        Arrays.fill(treeArray, 0);
        Arrays.fill(lSmaller, 0);
        Arrays.fill(lFlags, 0);
        for (int i = 0; i < size; i++) {
            int val = dscArray[i];
            lSmaller[i] = read(val - 1);
            if (lFlags[val] == 0) {
                update(val);
                lFlags[val] = i + 1;
            } else {
                lSmaller[i] -= lSmaller[lFlags[val] - 1];
            }
        }
    }

    void countRightLarger() {

        Arrays.fill(treeArray, 0);
        Arrays.fill(rLarger, 0);
        Arrays.fill(rFlags, 0);
        for (int i = size - 1; i >= 0; i--) {
            int val = dscArray[i];
            rLarger[i] = read(count - 1) - read(val);
            if (rFlags[val] == 0) {
                update(val);
                rFlags[val] = i + 1;
            }
        }
    }

    long countTriplets() {
        long sum = 0;
        for (int i = 0; i < size; i++) {
            sum += lSmaller[i] * rLarger[i];
        }
        return sum;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] a = new int[N];
        String[] strs = br.readLine().split(" ");
        for (int i = 0; i < N; i++)
            a[i] = Integer.parseInt(strs[i]);
        Triplets sol = new Triplets(N, a);
        sol.countLeftSmaller();
        sol.countRightLarger();
        System.out.println(sol.countTriplets());
    }
}