Find a Sorted Subsequence of size 3


Difficulty Level Medium
Frequently asked in Amazon Bloomberg Facebook Factset Google Oracle Uber Yahoo
Array

Problem Statement

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

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

Implementation

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 n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    FindTriplet(a,n);
    return 0;
}

Java Program for Find a Sorted Subsequence of size 3

import java.util.Scanner;
class sum
{
    public static 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)
           {
              System.out.println("Triplet found is: " + array[lesser[j]] + " " + array[j] + " " + array[greater[j]]);
              return;
           }
       }
        System.out.println("No such triplet found");
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        FindTriplet(a,n);
    }
}
7
1 4 2 6 9 3 5
Triplet found is: 1 4 9

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.

References