Be the first user to complete this post

Add to List 
Find the Increasing Triplet Subsequence 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: BruteForce 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.length1] =Rmax.length1
 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:
Output:
Triplet 1 7 11
Also Read: