Optimal way to check for number of triplets where a[k]

Question

I'm solving a problem where I have to find number of triplets of Ai, Aj, and Ak such that Ak < Ai < Aj and i < j < k in an array .

The solution to this by brute force is trivial but has complexity O(N^3). What is the optimal way to solve this?

The output size itself could be O(n^3), for a reversely sorted list (or some other permutation, just noticed the order of indices is not the same as order of elements) — amit, May 16 '15 at 20:29
for array :1 6 3 4 7 4 triplet is 1 i.e 6, 7, 4. (i=2, j=5, k=6) — Cyclotron3x3, May 16 '15 at 20:34
Are you looking for the triplets themselves or number of triplets? — amit, May 16 '15 at 20:40
possible duplicate of [interviewstreet Triplet challenge](http://stackoverflow.com/questions/13928575/interviewstreet-triplet-challenge) — Peter de Rivaz, May 16 '15 at 20:57
@Peter: You've missed the the change in ordering. In the post you've linked to, fixing a choice of `j` lets you split the condition into *independent* tests on `i` and `k` which drastically simplifies the problem. — , May 16 '15 at 21:05
I wonder if it's possible to solve this in O(n*log(n)) with some kind of augmented mergesort, [like with the problem of counting inversions](http://stackoverflow.com/questions/4552591/how-to-find-the-number-of-inversions-in-an-array). — user2357112, May 16 '15 at 21:50
If you break the list up into three intervals, I'm pretty sure you can count in `O(n)` or maybe `O(n lg n)` time the number of triples where `i`, `j`, and `k` come from the three intervals. I haven't yet figured out how to use this in a complete algorithm that beats `O(n^2)`. — , May 18 '15 at 00:37

Peter de Rivaz · Accepted Answer · 2015-05-18T18:27:22.583

2

This is an O(n^2) approach that fixes i and iterates over the rest of the array in reverse order, keeping track of the number of elements below a[i].

def count_triplets(a):
    """Count the number of triplets a[k]<a[i]<a[j] for i<j<k"""
    t = 0
    for i,ai in enumerate(a):
        kcount = 0 # The number of elements smaller than a[i]
        for x in a[:i:-1]:
            if x<ai:
                kcount += 1
            elif x>ai:
                t += kcount
    return t


A=[1,6,3,4,7,4]
print count_triplets(A)

Worked example

For the given array array the interesting case is when i is equal to 1 and ai is equal to 6.

The program now works backwards over the remaining entries in the array as follows:

x = 4
x < ai so kcount increased to 1
x = 7
x > ai so t increased by kcount, i.e. t increased to 1
x = 4
x < ai so kcount increased to 2
x = 3
x < ai so kcount increased to 3

All other values of i don't end up increasing t at all, so the final value for t is 1.

TEST CODE

The Hackerrank site wants the code to support a number of inputs. The code below passes all tests.

N=input()
for n in range(N):
    A=map(int,raw_input().split())
    print count_triplets(A)

edited May 18 '15 at 18:27

answered May 16 '15 at 21:22

Peter de Rivaz

33,126
4
46
75

I think you got the order reversed. It looks like this code uses k – user2357112 May 16 '15 at 21:27
Do you have a test case that would give a different answer? Note that the inner loop is working in reverse order. – Peter de Rivaz May 16 '15 at 21:29
The question asks for the triplets, not just the total number? – petrelharp May 17 '15 at 04:34
@PeterdeRivaz can you please provide an example demonstrating how your algo is giving correct answer . For A=[1,6,3,4,7,4] number of triplets should me 1. I don't see how your algo will give that. I am not a python programmer so unable to figure out few lines. – Cyclotron3x3 May 17 '15 at 07:17
@Ashish I've added an example showing how the algorithm works for this array. – Peter de Rivaz May 17 '15 at 07:35
@petrelharp The question body asks about triplets, but the headline says "number of triplets" (see also the clarification about that in the comments below the question). – Thomas May 17 '15 at 11:13
@PeterdeRivaz I have written in java what you have written in python but its giving me wrong answer in most test cases. `for(int i=0;ii;j--){ if(a[j]a[i]) k+=t; } } System.out.println(""+k); ` – Cyclotron3x3 May 18 '15 at 18:01
Can you post a failing test case or a link to the problem? – Peter de Rivaz May 18 '15 at 18:09
This is the question https://www.hackerrank.com/contests/101hack24/challenges/twisty-tuple – Cyclotron3x3 May 18 '15 at 18:21
I've tried my Python code and it passed all tests, so perhaps you have some problem with reading the input and converting it to integers? – Peter de Rivaz May 18 '15 at 18:28
@PeterdeRivaz I got it its because you have increased kcount at wrong place . i.e it should be if x>ai: kcount += 1 elif x – Cyclotron3x3 May 18 '15 at 18:40
@Ashish I've rejected your edit because it makes the code fail the Hackerrank tests - and return the wrong answer even for the single test case in the original question. I suspect it is a good edit for your code, but bad for the Python version for some reason. – Peter de Rivaz May 18 '15 at 18:48
@PeterdeRivaz but in my case it passed all test cases. Its strange that language implementation is a concern here. – Cyclotron3x3 May 18 '15 at 18:51
@Ashish I agree this is very strange, but without seeing your entire code it is hard to know what might be causing the difference. – Peter de Rivaz May 18 '15 at 18:53
@PeterdeRivaz can you try once to run the inner loop from i+1 to end .instead of running from reverse. I hope that is the difference . – Cyclotron3x3 May 18 '15 at 19:01
@Ashish Yes, that works (although in the comment you had above it looked like you were running the j loop in reverse) – Peter de Rivaz May 18 '15 at 19:03
@PeterdeRivaz I was trying to copy your code to java that time. later I changed as we have to keep in mind the constraint i < j < k . as a[j] > a[i] and a[k] < a[i]. so first finding larger element and then finding smaller one and adding them does the trick . But the core remains your Algo with slight modification . – Cyclotron3x3 May 18 '15 at 19:06

Optimal way to check for number of triplets where a[k]

1 Answers1

Worked example

TEST CODE