Find a sorted subsequence of size 3 in linear time | C ++ Program for above approach ; Function to find the triplet ; If number of elements < 3 then no triplets are possible ; track best sequence length ( not current sequence length ) ; min number in array ; least max number in best sequence i . e . track arr [ j ] ( e . g . in array { 1 , 5 , 3 } our best sequence would be { 1 , 3 } with arr [ j ] = 3 ) ; save arr [ i ] ; Iterate from 1 to nums . size ( ) ; this condition is only hit when current sequence size is 2 ; update best sequence max number to a smaller value ( i . e . we 've found a smaller value for arr[j]) ; store best sequence start value i . e . arr [ i ] ; Increase best sequence length & save next number in our triplet ; We 've found our arr[k]!  Print the output ; No triplet found ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void find3Numbers ( vector < int > & nums ) { if ( nums . size ( ) < 3 ) { cout << " No ▁ such ▁ triplet ▁ found " ; return ; } int seq = 1 ; int min_num = nums [ 0 ] ; int max_seq = INT_MIN ; int store_min = min_num ; for ( int i = 1 ; i < nums . size ( ) ; i ++ ) { if ( nums [ i ] == min_num ) continue ; else if ( nums [ i ] < min_num ) { min_num = nums [ i ] ; continue ; } else if ( nums [ i ] < max_seq ) { max_seq = nums [ i ] ; store_min = min_num ; } else if ( nums [ i ] > max_seq ) { seq ++ ; if ( seq == 3 ) { cout << " Triplet : ▁ " << store_min << " , ▁ " << max_seq << " , ▁ " << nums [ i ] << endl ; return ; } max_seq = nums [ i ] ; } } cout << " No ▁ such ▁ triplet ▁ found " ; } int main ( ) { vector < int > nums { 1 , 2 , -1 , 7 , 5 } ; find3Numbers ( nums ) ; }