Increasing Triplet Subsequence

Easy
0/40
Average time to solve is 15m
8 upvotes
Asked in company
Uber

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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 .

Sample Input 1:

2
3
2 1 3
5
1 2 0 4 5

Sample Output 1:

False
True

Explanation of Sample Input 1:

Test Case 1:
We try to find i, j, k such that ‘i < j < k’ and ‘ARR[i] < ARR[j] < ARR[k]’ but we can see that there is no such pair as only one possible pair exists:
‘2 > 1 < 3’ so it fails our required condition hence we returned ‘False’.

Test Case 2:
For this test case size of the array is ‘5’ and elements of the array are [1, 2, 0, 4, 5] so the pair of indices possible that satisfy required conditions are shown below:

‘i=0, j=1, k=2’ but ‘ARR[0] < ARR[1] > ARR[2] as 1 < 2 >0.
‘i=1, j=2, k=3 but ‘ARR[1] > ARR[2] < ARR[3] as 2 > 0 < 4.
‘i=2, j=3, k=4 now ARR[2] < ARR[3] < ARR[4] as 0 < 4 < 5.
Hence we return ‘True’ as such a pair of indices is present in the array.

Sample Input 2:

2
3
1 1 1
5
1 2 3 4 5

Sample Output 2:

False
True

Explanation of Sample Input 2:

Test Case 1:
We try to find i, j, k such that ‘i < j < k’ and ‘ARR[i] < ARR[j] < ARR[k]’ but we can see that there is no such pair as only one possible pair exists:
‘1 = 1 = 1’ so it failed our required condition hence we returned ‘False’.

Test Case 2:
For this test case size of the array is ‘5’ and elements of the array are [1, 2, 3, 4, 5] so the pair of indices possible  that satisfy required conditions are shown below:

‘i=0, j=1, k=2’  ‘ARR[0] < ARR[1] < ARR[2] as 1 < 2 < 3.
‘i=1, j=2, j=3  ‘ARR[1] < ARR[2] < ARR[3] as 2 < 3 < 4.
‘i=2, j=3, k=4 now ARR[2] < ARR[3] < ARR[4] as 3 < 4 < 5.
Hence we return ‘True’ as such a pair of indices is present in the array.
Hint

Try to check possible tuples of ‘i,  j,  k’.

Approaches (3)
Brute Force

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

O(N ^ 3), Where ‘N’ is the size of an array.

 

As each loop takes O(N) time so O(N) * O(N) * O(N) = O(N ^ 3)

Space Complexity

O(1). 

 

No extra space is being used.

Code Solution
(100% EXP penalty)
Increasing Triplet Subsequence
Full screen
Console