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

Algorithm Working

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
   //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;
}
Try It

 


Next > < Prev
Scroll to Top