# Sorted Subsequence of Size 3

Posted: 1 Jan, 2021

Difficulty: Moderate

#### 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
```

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.

- Let the element picked be
- 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 element picked must be greater than
- 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.

- The element picked must be greater than
- So,
**p < q < r**and**i < j < k**. - Hence, the three elements-
**p, q and r**form the required subsequence.

Approach 2

- 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.

- If it is smallest in the subarray
- 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 it is the largest in the subarray
- 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.

- We run a loop to check if there exists a smaller element in the subarray

Approach 3

- 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 ] ]}.**

Approach 4

- 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.

- Update
- 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.

SIMILAR PROBLEMS

# Loudspeakers

Posted: 17 Nov, 2021

Difficulty: Moderate

# Insertion Sort

Posted: 30 Nov, 2021

Difficulty: Easy

# Subarrays With Zero Sum

Posted: 1 Dec, 2021

Difficulty: Easy

# Find Student

Posted: 1 Dec, 2021

Difficulty: Easy

# Smaller Than Triplet Sum

Posted: 1 Dec, 2021

Difficulty: Moderate