Increasing Triplet Subsequence

Posted: 19 Mar, 2021
Difficulty: Easy


Try Problem

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.
You do not need to print anything; it has already been taken care of. Just implement the function.


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

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