Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find Increasing Triplet Sub-sequence

Objec­tive: Given an inte­ger array A[1..n], find an instance of i,j,k where 0 < i < j < k <= n and A[i] < A[j] < A[k].

Exam­ple :

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 Solu­tion : Brute-Force O(n^2) — Use two for loops and try every triplet till you find the increas­ing triplet.

Bet­ter Solu­tion : 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 Tra­verse the main array and check for the ele­ment with the fol­low­ing con­di­tion and print it.

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

Code:


Out­put:

Triplet 1 7 11

You may also like...