Form a Triangle

The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow. The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array. The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.

For each test case, print a single line containing either “YES”(without quotes) if it is possible to form a non-degenerate triangle, otherwise “NO”(without quotes). The output of each test case will be printed in a separate line.

1 <= T <= 100 3 <= N <= 10 ^ 3 0 <= ARR[i] <= 10 ^ 9 Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of elements in the array, and 'ARR[i] denotes the elements of the array. Time Limit: 1 sec.

In the first test case, if we choose the sides as { 2,3,4} or {2,2,1} or {2,2,3} then it is possible to form a non-degenerate triangle. In the second test case, if we choose sides as {5,3,7}, then it is possible to form a non-degenerate triangle.

In the first test case, there is no possible way to choose three elements such that they will form the sides of a triangle. In the second test case, if we choose the sides as {7,12,9} or {12,9,20}, then it is possible to form a non-degenerate triangle

Brute Force

Suppose that 'X', 'Y' and 'Z' are the sides of a triangle, so a non-degenerate triangle can be formed if the following three conditions are satisfied:

'X' + 'Y' > 'Z'
'Y' + 'Z' > 'X'
'X' + 'Z' > 'Y'

The idea is to explore all the possible ways of choosing 3 elements from the given array/list and check if any combination satisfies the constraints for making a non-degenerate triangle or not.

We will Iterate through the array and pivot each element as the first side of the triangle. Let’s say we are at ‘I’ th index, So we will pivot ‘I’th index as our first side of the triangle.
And for the second side of the triangle, we will start exploring from the next index of ‘I’ and pivot each element from (I+1) till the end as the second side of the triangle. Let’s say we are at the ‘J’th index, So we will pivot the ‘J’th index as our second side of the triangle.
And for the third side of the triangle we will iterate from the next index of ‘J’ till the end of the array/list and pivot each element from (J+1) to till the end as the third side of the triangle, say at index ‘K’.
For each triplet, we will check whether it satisfies all the conditions for forming a non-degenerate triangle or not, I.e

1. 'ARR'[I] +'ARR'[J] >'ARR'[K]

2. 'ARR'[J] + 'ARR'[K] > 'ARR'[I]

3. 'ARR'[I] + 'ARR'[K] > 'ARR'[J]

If yes, then return true otherwise we will go to the next triplet.
If no triplet can become sides of a non-degenerate triangle, return false.

Time Complexity

O(N ^ 3), where ‘N’ is the number of elements in the given array/list.

We are pivoting every element as the first side of the triangle and for each first side of the triangle we are going to pivot all the element from next of the first side as the second side of the triangle and for every second side, we are pivoting next element from the second side, as the third side of the triangle. So in the worst case, when there is no triplet that forms a non-degenerate triangle, we have to check all the triplets. Thus, the total time complexity will be O(N ^ 3).

Space Complexity

O(1).

We are not using any extra space. Thus, the space complexity will be O(1).

Problem statement

Sample Input 1 :

Sample Output 1:

Explanation of Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation of Sample Input 2: