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.
Conversely, if you have k (k >= 3) positive real numbers a1, a2, a3, ..., ak where a1 <= a2 <= a3 <= ... <= ak and a1 + a2 + a3 + ... + ak-1 > ak, then there always exists a polygon with k sides whose lengths are a1, a2, a3, ..., ak.
The perimeter of a polygon is the sum of lengths of its 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.
Example 1:
Input: nums = [5,5,5] Output: 15 Explanation: The only possible polygon that can be made from nums has 3 sides: 5, 5, and 5. The perimeter is 5 + 5 + 5 = 15.
Example 2:
Input: nums = [1,12,1,2,5,50,3] Output: 12 Explanation: The polygon with the largest perimeter which can be made from nums has 5 sides: 1, 1, 2, 3, and 5. The perimeter is 1 + 1 + 2 + 3 + 5 = 12. We cannot have a polygon with either 12 or 50 as the longest side because it is not possible to include 2 or more smaller sides that have a greater sum than either of them. It can be shown that the largest possible perimeter is 12.
Example 3:
Input: nums = [5,5,50] Output: -1 Explanation: There is no possible way to form a polygon from nums, as a polygon has at least 3 sides and 50 > 5 + 5.
Constraints:
3 <= n <= 1051 <= nums[i] <= 109To solve #2971 Find Polygon With the Largest Perimeter, we rely on the geometric rule that a valid polygon exists only if the largest side is strictly smaller than the sum of the remaining sides. This insight naturally leads to a greedy strategy.
First, sort the array of side lengths in non-decreasing order. As we iterate through the array, maintain a running prefix sum representing the total length of all previous sides. For each element treated as the current largest side, check whether largest < sum_of_previous_sides. If this condition holds, the sides up to this point can form a valid polygon, and their total sum becomes a candidate perimeter.
By scanning from smaller to larger sides, we maximize the perimeter whenever the polygon condition is satisfied. Sorting ensures that the largest side is always the current element, simplifying validation. The overall approach runs in O(n log n) time due to sorting, while the traversal itself is linear.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Sorting and Prefix Sum | O(n log n) | O(1) extra space (or O(n) if prefix array is used) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Sort the array.
Use greedy algorithm. If we select an edge as the longest side, it is always better to pick up all the edges with length no longer than this longest edge.
Note that the number of edges should not be less than 3.
This approach involves sorting the array of side lengths and then iterating through it to find the largest valid polygon, specifically checking sets of three sides. By sorting, we can easily make sure that when checking three sides, the largest is the last one, allowing a simple perimeter check.
Sort the array in non-decreasing order and start checking from the third last element using a sliding window of three elements to check if they form a valid polygon (triangle) using the property: if a <= b <= c, a triangle forms if a + b > c.
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1), as no extra space proportional to input size is used.
1def largestPerimeter(nums):
2 nums.sort(reverse=True)
3 for i in range(len(nums) - 2In this implementation, the array is sorted in descending order. We iterate through the sorted array from the largest element and check each triplet to see if they can form a valid triangle. As soon as we find a valid triplet, we return its perimeter. If no valid polygon is found throughout the checks, we return -1.
This approach involves checking each combination of three different side lengths from the list to see if they can form a valid polygon (triangle). For each valid combination found, we will calculate its perimeter, and keep track of the maximum perimeter obtained.
This naive method is straightforward but can be inefficient for larger lists due to its O(n^3) complexity. However, it can be insightful for understanding triangle properties in small datasets.
Time Complexity: O(n^3) due to triple nested loops.
Space Complexity: O(1), apart from input storage no extra space is required.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The main data structure used is an array along with a running prefix sum variable. Sorting the array allows efficient validation of the polygon condition while scanning the elements in order.
Sorting ensures that when we evaluate a side, it is the largest among the selected sides. This simplifies checking the polygon inequality rule, where the largest side must be smaller than the sum of the remaining sides.
Yes, variations of this problem appear in technical interviews because it combines greedy reasoning with sorting and prefix sums. It tests a candidate's understanding of mathematical constraints and efficient array traversal.
The optimal approach uses a greedy strategy combined with sorting. After sorting the sides, maintain a running prefix sum and check whether the largest side is smaller than the sum of the previous sides. If the condition holds, those sides can form a valid polygon with that total perimeter.
This brute force implementation tests every combination of three distinct sides in the sorted array. If a triplet satisfies the triangle inequality, the perimeter is calculated and compared against the current maximum to find the largest valid perimeter.