Last Updated: 1 Jan, 2021
Sorted Subsequence of Size 3
Moderate
Asked in companies
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.
Follow Up:
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
Approaches
- 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.
- The idea is to find an element such that, there exists one element smaller than itself on the left side of the array and another element greater than itself on the right side of the array.
- Consider an element in the array present at index i.
- In order to check if the element has a smaller element than itself on the left side of the current index, we can just check if the current element is the smallest element in the subarray A[0, i] or not.
- If it is smallest in the subarray A[0, i] then, there exists no smaller element.
- Otherwise, a smaller element exists.
- Similarly to check if the element has a larger element than itself on the right side of the current index, we can just check if the current element is the largest element in the subarray A[i, N-1] or not.
- If it is the largest in the subarray A[i, N-1] then, there exists no larger element.
- Otherwise, a larger element exists.
- If both, a smaller and a larger element exist then, we have found the required subsequence which is: {smaller element in A[0, i-1], A[i], larger element in A[i+1, N-1]}.
- The above approach can be implemented by iterating through the array.
- For each element in the array:
- We run a loop to check if there exists a smaller element in the subarray A[0, i-1].
- And another loop to check if there exists a larger element in the subarray A[i+1, N-1].
- If both these elements exist, we have found the required subsequence.
- The idea is to find an element such that, there exists one element smaller than itself on the left side of the array and another element greater than itself on the right side of the array.
- This approach is similar to the previous one but instead of running a nested loop for every element in the array, we can precompute the results for larger and smaller elements for all elements.
- This can be done by using two auxiliary arrays- smaller and larger. For any index ‘i’-
- Smaller[i] stores the index of the element which is smaller than A[i] and is present on the left side of the current index i.e. in the subarray A[0, i-1]. If there is no such element, it stores -1.
- Larger[i] stores the index of the element which is larger than A[i] and is present on the right side of the current index i.e. in the subarray A[i+1, N-1]. If there is no such element, it stores -1.
- Now, we traverse both the auxiliary arrays - smaller and larger, and find the index ‘j’ for which both smaller[j] != -1 and larger[j] != -1.
- So, the required subsequence would be: {A[ smaller[ j ] ], A[ j ], A[ larger[ j ] ]}.
- The idea is to find a pair of elements which will form the first two elements of the required subsequence, say P and Q. If we can find a third element which is greater than both these elements, say R, then our search for the subsequence is complete.
- The triplet {P, Q, R} is the required subsequence, where P < Q < R.
- In order to implement this approach, we create three variables, small, middle and minimum, and initialize them to INFINITY.
- Small and middle are used to store the first two elements of the subsequence. Whereas minimum stores the minimum element found up till the current iteration/index.
- In order to check if we have found the first two elements or not, we create another variable called found and initialize it to false (as initially, we haven’t found the first two elements).
- Now, we iterate through the given array.
- During the iteration, if the current element <= minimum, update minimum with the current element.
- Otherwise, if the current element <= middle OR if we have already found the first two elements i.e. if found = true,
- Update middle = current element.
- Update small = minimum.
- Set, found = true.
- Now, we have found two elements in the array, small and middle, such that small < middle, and they form a subsequence of size 2.
- Otherwise, we have found an element which is greater than small and middle. Store its index in a variable, say ‘k’.
- This will be our third element of the subsequence.
- Return the subsequence {small, middle, A[k]}.
- If after complete iteration we haven’t found the subsequence then return an empty sequence.