|
Be the first user to complete this post
|
Add to List |
125. Find the Increasing Triplet Sub-sequence in an array
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]
Output:
Triplet 1 7 11