Sorted Subsequence of Size 3

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
CultfitAmazonWalmart

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}.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
7 8 6 1 -2
6
10 0 2 1 2 4
Sample Output 1:
No 
Yes
Explanation For Sample Input 1:
For the first test case, we have an array: [7, 8, 6, 1, 2] for the first test case.

There exists no subsequence of size 3, whose elements are in increasing order. Hence, we print “No”.

For the second test case, we have, array: [10, 0, 2, 1, 2, 4].

The possible subsequences of size 3, whose elements follow increasing order are {0, 2, 4}, {0, 1, 2}, {0, 1, 4}, {1, 2, 4}. So, print “Yes”.
Sample Input 2:
2
6
10 20 30 40 50 60
4
10 15 22 31
Sample Output 2:
Yes
Yes
Hint

A brute force approach could be to run three nested loops to find a subsequence which satisfies the given condition.

Approaches (4)
Brute Force
  • 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.
Time Complexity

O(N ^ 3) per test case, where N is the number of elements in the array.

 

In the worst case, there exist three nested loops. Hence, the overall complexity is O(N ^ 3).

Space Complexity

O(1) per test case.

 

In the worst case, no extra space is required.

Code Solution
(100% EXP penalty)
Sorted Subsequence of Size 3
Full screen
Console