Home » Technical Interview Questions » Array Interview Questions » Find a Sorted Subsequence of size 3

Find a Sorted Subsequence of size 3


Reading Time - 4 mins


Difficulty Level Medium

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

READ  Length of Longest Fibonacci Subsequence

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.

READ  Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’

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.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions