Problem Description
You are given an array of positive integers nums of length n. A polygon is a closed plane figure that has at least 3 sides. The longest side of a polygon is smaller than the sum of its other sides. Return the largest possible perimeter of a polygon whose sides can be formed from nums, or -1 if it is not possible to create a polygon.
Key Insights
- A valid polygon requires at least 3 sides.
- The longest side must be less than the sum of the other sides.
- Sorting the array helps in easily checking the polygon condition from the largest side downwards.
- The perimeter is maximized by using the largest possible sides that satisfy the polygon inequality.
Space and Time Complexity
Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(1) - no additional data structures are used, only a few variables.
Solution
To solve the problem, we first sort the array of side lengths in non-decreasing order. By checking from the largest side down to the smallest, we can identify the first triplet of sides that satisfies the polygon inequality (where the sum of the two smaller sides is greater than the longest side). If such a triplet is found, we return their sum as the perimeter. If no valid triplet is found by the end of the checks, we return -1.