216. Biggest Fence Triangle
A farmer has several wooden sticks with the lengths given in sides. He wants to build a triangular fence by using exactly three different sticks as the three sides, without breaking any of them. A fence can only be built when the three sticks form a real triangle: the sum of the two shorter lengths must be strictly greater than the longest length. Flat shapes, where the two shorter sticks only just reach the end of the longest one, are not allowed.
Return the largest possible perimeter (the sum of the three lengths) among all fences that can be built. If no three sticks make a valid triangle, return 0.
For example, from the sticks [2, 3, 10, 4] the sticks 2, 3 and 4 make a triangle with perimeter 9, while 10 is too long to be used.
Example 1
- Input:
- sides = [3,8,4,9,2]
- Output:
- 21
- Explanation:
Sorted from longest: 9, 8, 4, 3, 2. The triple (9, 8, 4) fails since 8 + 4 is not greater than 9, and (8, 4, 3) fails since 4 + 3 is less than 8, but (4, 3, 2) works: perimeter 9.
Example 2
- Input:
- sides = [1,1,10]
- Output:
- 0
- Explanation:
1 + 1 is not greater than 10, so no fence is possible: 0.
Example 3
- Input:
- sides = [6,6,6]
- Output:
- 18
- Explanation:
An equilateral triangle with perimeter 18.
Constraints
3 ≤ sides.length ≤ 104
1 ≤ sides[i] ≤ 108
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)