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

**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...

*Related*