# Find a sorted subsequence of size 3

## In the given unsorted array of integers. We need to find a sorted subsequence of size 3.

Let three elements be array[i], array[j], array[k] then, array[i] < array[j] < array[k] for i< j < k.
If there are multiple triplets then, print any one of them.

### Example

a) Input array be: [22, 21, 19, 15, 16, 12, 35]
Output: 15, 16, 35

b) Input array be: [3, 4, 6, 9]
Output: 3, 4, 6 (or) 3, 4, 9 (or) 3, 6, 9 (or) 4, 6, 9

c) Input array be: [12, 13, 6, 5, 3, 2, 1]
Output: No triplet found.

Time Complexity : O(n)

## Algorithm

a. Create two auxiliary arrays lesser[] and greater[] same as size of input array.

b. In lesser array,
1) lesser[0] = -1
2) lesser[i] will stores the index of number which is less than array[i] and is on left side of array[i].
3) If there is no such element, then lesser[i] = -1

c. In greater array,
1) greater[N-1] = -1, last element
2) greater[i] will stores the index of number which is greater than array[i] and is on right side of array[i].
3) If there is no such element, then greater[i] = -1

d. After getting both smaller and greater, traverse both smaller and greater and find if at same index both smaller[i] and greater[i] not equal to -1, if found then print array[smaller[i]], array[i] and array[greater[i]].

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

void FindTriplet(int array[], int n)
{
//lesser array
//first element = -1
//lesser[i] = index of element lesser in the left side of array[i]
//lesser[i] = -1 if no such element found
int *lesser = new int[n];
int min = 0;
lesser[0] = -1;
for (int i = 1; i < n; i++)
{
if(array[i] <= array[min])
{
min = i;
lesser[i] = -1;
}
else
{
lesser[i] = min;
}
}
//greater array
//last element = -1
//greater[i] = index of element gretaer in the right side of array[i]
//greater[i] = -1 if no such element found
int *greater = new int[n];
int max = n-1;
greater[n-1] = -1;
for (int k = n-2; k >= 0; k--)
{
if (array[k] >= array[max])
{
max = k;
greater[k] = -1;
}
else
{
greater[k] = max;
}
}
//if both smaller and greater has element otherthan -1 at same index.
//print them if found.
//else, traverse till end
for (int j = 0; j < n; j++)
{
if (lesser[j] != -1 && greater[j] != -1)
{
cout<<"Triplet found is: ";
cout<<"["<<array[lesser[j]]<<", "<<array[j]<<", "<<array[greater[j]]<<"]";
return;
}
}
cout<<"No such triplet found";
//free the dynamic memory
delete [] lesser;
delete [] greater;
return;
}

//Main function
int main()
{
int input_array[] = {22, 21, 19, 15, 16, 12, 35};
int size = sizeof(input_array)/sizeof(int);
FindTriplet(input_array,size);
return 0;
}``````

Scroll to Top