Solution


Approach 1: Sort

Intuition

Without loss of generality, say the sidelengths of the triangle are . The necessary and sufficient condition for these lengths to form a triangle of non-zero area is .

Say we knew already. There is no reason not to choose the largest possible and from the array. If , then it forms a triangle, otherwise it doesn't.

Algorithm

This leads to a simple algorithm: Sort the array. For any in the array, we choose the largest possible : these are just the two values adjacent to . If this forms a triangle, we return the answer.

Complexity Analysis

  • Time Complexity: , where is the length of A.

  • Space Complexity: .


Analysis written by: @awice.