Find a Sorted Subsequence of size 3

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;
}

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

References