Find Increasing Triplet Sub-sequence

Objective: Given an integer array A[1..n], find an instance of i,j,k where 0 < i < j < k <= n and A[i] < A[j] < A[k].

Example :

int arrA[] = { 10, 9, 4, 3, 2, 1, 7, 3, 1, 11, 2, 6, 9 };
Output :
Increasing triplets are

1, 7, 11
1, 2, 6
1, 3, 9

likewise you can find more triplets.

Approach:

Naive Solution : Brute-Force O(n^2) – Use two for loops and try every triplet till you find the increasing triplet.

Better Solution : O(n)

  • Cre­ate 2 Aux­i­lary Arrays say Lmin[] and Rmax[] of the same size as main array
  • Put Lmin[0]=0 and Rmax[Rmax.length-1] =Rmax.length-1
  • Tra­verse the main array and fill the Lmin array with the index posi­tion which has the min­i­mum value so far
  • Tra­verse the main array back­words and fill the Rmax array with the index posi­tion which has the max­imun value so far.
  • Now Traverse the main array and check for the element with the following condition and print it.

arrA[Lmin[i]] < arrA[i] && arrA[Rmax[i]] > arrA[i]

Code:


Output:

Triplet 1 7 11

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: