Problem Description
Given an array of integers representing side lengths, return the largest perimeter of a triangle that can be formed using any three of these lengths. If no valid triangle with non-zero area exists, return 0.
Key Insights
- A valid triangle can be formed if for any three sides a, b, and c (with a ≤ b ≤ c) the condition a + b > c holds.
- Sorting the array allows us to easily check the triangle inequality by considering consecutive triples.
- By iterating from the largest values, the first valid triangle found will have the largest possible perimeter.
Space and Time Complexity
Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(1) if sorting is done in-place, or O(n) if a new sorted array is created.
Solution
The solution starts by sorting the array in non-decreasing order. Once the array is sorted, we iterate from the end of the array backwards over every consecutive triplet (i, i-1, i-2). For each triplet, we check if the sum of the two smallest sides is greater than the largest side. If the condition is satisfied, we can form a valid triangle and the sum of this triplet is the largest possible perimeter (since we are checking larger elements first). If no valid triplet is found, we return 0.