CODEWITHSUNDEEP
arraysalgorithm
Cyclotron3x3
Cyclotron3x3

Reputation: 2229

Optimal way to check for number of triplets where a[k]<a[i]<a[j] for all i<j<k in an array

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?

Upvotes: 2

Views: 1370

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

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)

Upvotes: 2

Related Questions