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)

Create 2 Auxilary Arrays say Lmin[] and Rmax[] of the same size as main array
Put Lmin[0]=0 and Rmax[Rmax.length-1] =Rmax.length-1
Traverse the main array and fill the Lmin array with the index position which has the minimum value so far
Traverse the main array backwords and fill the Rmax array with the index position which has the maximun 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: Run This Code

Output :

Triplet 1 7 11
__________________________________________________
Top Companies Interview Questions..-

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

Like this: Like Loading...