Sorted Subsequence of Size 3

Posted: 1 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

You are given an array consisting of N elements and you need to find a subsequence consisting of three elements such that the elements, in the subsequence, are in strictly increasing order.

Note:
``````There may be multiple such subsequences, so return any one of them.
``````
Example:
``````Let the array be [100, 22, 13, 45, 59, 26]. The possible subsequences of size 3, whose elements follow increasing order are {22, 45, 59}, {13, 45, 59}.
``````
Input format:
``````The very first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of every test case contains an integer ‘N’ denoting the number of elements present in the array.

The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.
``````
Output format:
``````For each test case, print “Yes” if such a subsequence exists otherwise, print “No”.
``````
Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.

The function returns any one of the possible subsequences. If no such subsequence exists, return an empty sequence.
``````
``````Can you solve the problem using constant extra space i.e. O(1) space complexity?
``````
Constraints:
``````1 <= T <= 100
3 <= N <= 10^4
-10^5 <= Array[i] <= 10^5

Time Limit: 1 sec
``````
Approach 1
• The idea is to run three nested loops to find a subsequence which satisfies the given condition.
• Each loop picks one element of the subsequence.
• The first loop picks the first element for the subsequence.
• Let the element picked be p present at index i in the array.
• The second nested loop iterates over the elements present after index i, to the pick the second element for the subsequence.
• The element picked must be greater than p.
• Let the element picked be q present at index j in the array.
• The third nested loop iterates over the elements present after index j, to the pick the third element for the subsequence.
• The element picked must be greater than q.
• Let the element picked be r present at index k in the array.
• So, p < q < r and i < j < k.
• Hence, the three elements- p, q and r form the required subsequence.