Last Updated: 19 Mar, 2021
Increasing Triplet Subsequence
Easy
Asked in company
Ninja is thinking of developing a game based on “Teen Patti” where a user will be provided with some number ‘N’ or in technical terms with an array “ARR[i]” and the user has to find out if there exists a triplet of indices (i, j, k) such that ‘i < j < k’ and ‘ARR[i] < ARR[j] <ARR[k]’ holds true. If such a pair of indices exists the user has to return ‘True’ else he has to return ‘False’.
Your task is to help Ninja find out such triplets indices.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains a single integer ‘N’ denoting the size of the array.
The next line contains ‘N’ space-separated strings denoting the values of elements of the given array.
Output Format:
For each test case, print a single line containing ‘True’ or ‘False’ as per the given condition.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 5
1 <= N <= 5000
0 <= i < j < k <= N
1 <= ARR[i] <= 10 ^ 9
Where ‘T’ represents the number of test cases and ‘N’ represents the size of array 'i', 'j', 'k' represents the triplets indices, and ‘ARR[i]’ represents the elements of the array.
Time Limit: 1 second .
Approaches
The idea here is to check all possible tuples(i, j, k) that satisfy given conditions. For this, we will use 3 nested loops.
- In this approach, we go through each and every triplet’s indices and check whether such pair exists ‘i < j < k and arr[i] < arr[j] < arr[k]’.
- So for this, we traverse through the array by running three nested loops so there will be three variables i, j, k. ‘I’ is the variable from the first loop ‘j’ is the variable from the second loop and starts from ‘i+1’ and ‘k’ is the variable from the third loop and starts from ‘j+1’.
- So now we check:
- If ‘arr[i] < arr[j] < arr[k]’ or we can say such a pair exists and return ‘True’.
- Else traverse the array further.
- After traversing the whole array if we are not able to find any tuple(i, j, k) that satisfies the required conditions then we will return false.
The idea here is to optimize time complexity. For this we use two auxiliary arrays.
- For optimizing our time complexity first we create an auxiliary array ‘smaller[0. . .n-1’]. ‘smaller[i]’ helps in storing the index of a number that is smaller than ‘arr[i]’ and is on the left side of our main array ‘arr’. The array contains -1 if there is no such element.
- We run a loop i starting from 1 to N - 1 and initialize a variable ‘min’ to ‘0’ and check
- If ( arr[i] > arr[min] )
- Then do, Smaller[i] = min.
- Else
- Then do, Smaller[i] = -1.
- min = i
- Now we create another auxiliary array greater[0. . .n-1]. ‘greater[i]’ helps in storing the index of a number that is greater than arr[i] and is on the right side of ‘arr[i]’. The array contains -1 if there is no such element.
- We run a loop i starting from N - 2 to 0 and initialize a variable max to ‘N - 1’ and check
- If ( arr[i] < arr[max] )
- Then do, greater[i] = min.
- Else
- Then do, greater[i] = -1.
- Then do, max = i.
- Now we traverse both smaller[] and greater[] and try to find out the number which has both a greater number on the right side and a smaller number on the left side.
- If we find out that number we will return “True” else “False”.
The idea here is to optimize space. To do this first we will find ‘arr[i]’ and ‘arr[j]’ such that arr[i] < arr[j] then we look for arr[k] such that arr[j] < arr[k].
Algorithm:
- First we only need to find out the two elements ‘arr[i]’ < ‘arr[j]’ and i < j. This can be done with just one loop over the size of the array. For instance, while keeping track of the min element, it’s easy to find any subsequent element that is greater than it. Thus we have our ‘arr[i]’ and ‘arr[j]’.
- Now, while iterating over the array we can easily keep track of min and eventually update it to the lower value. And we can also update ‘arr[i]’ and ‘arr[j]’ to lower values.
- Now, as soon as we have ‘arr[i]’ and ‘arr[j]’ values, we can immediately start looking for the subsequent elements in the same loop for an arr[k] > arr[j]. Thus we can check for all three values arr[i] < arr[j] < arr[k] without using extra space.