# 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** :

intarrA[] = { 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:**

**Output**:

Triplet 1 7 11