Approach 1: Sort
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.
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.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.