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 found in the array then print any one of them.

## Example

**Input **

arr[] = {22, 21, 19, 15, 16, 12, 35}

**Output**

seq[] = {15, 16, 35}

**Input **

arr[] = {3, 4, 6, 9}

**Output **

seq[] = {3, 4, 6} (or) {3, 4, 9} (or) {3, 6, 9} (or) {4, 6, 9}

**Input **

arr[] = {12, 13, 6, 5, 3, 2, 1}

**Output**

No triplet found.

## Algorithm for Find a Sorted Subsequence of size 3

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

2. In lesser array,

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

3. In greater array,

- Greater[N-1] = -1, last element.
- Greater[i] will store the index of number which is greater than array[i] and is on the right side of array[i].
- If there is no such element, then greater[i] = -1

4. 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 for Find a Sorted Subsequence of size 3

#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 //if not found till end, print No triplet found 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; }

Triplet found is: [15, 16, 35]

## Complexity Analysis for Find a Sorted Subsequence of size 3

### Time Complexity

O(N) where N is the number of elements present in the array. Here we just iterate over the array three times and find the desired result by using some calculation. That’s why the above logic leads us to linear time complexity.

### Space Complexity

O(1) because the space we used here is constant. That’s why the above logic leads us to O(1) space complexity.