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] <= 109Problem Overview: You receive an array of integers representing side lengths. The goal is to select some of these sides to form a valid polygon with the largest possible perimeter. A polygon is valid only if the largest side is strictly smaller than the sum of the remaining sides.
The polygon rule generalizes the triangle inequality: maxSide < sum(otherSides). If this condition holds, the chosen sides can form a polygon. The challenge is finding the subset with the maximum perimeter while maintaining this constraint.
Approach 1: Brute Force Approach (O(n²) time, O(1) space)
Start by sorting the array so side lengths are processed in increasing order. For every potential largest side nums[i], compute the sum of all smaller sides and check whether the polygon condition holds. This often requires recomputing sums for each candidate, leading to quadratic time. If nums[i] < sum, a valid polygon exists using the first i + 1 sides, and its perimeter is sum + nums[i]. While simple, repeated summation makes this inefficient for large arrays.
This method is useful for understanding the geometric constraint behind polygon construction. It directly verifies the rule without relying on optimization techniques. However, interview settings usually expect a more efficient solution once the key inequality is recognized.
Approach 2: Sorting + Greedy Prefix Sum (O(n log n) time, O(1) space)
The optimal solution sorts the array and scans it once while maintaining a running prefix sum. Sorting ensures that when you examine a side nums[i], it is the largest among the chosen sides. The prefix sum represents the total length of all smaller sides.
During iteration, check the polygon condition: nums[i] < prefixSum. If true, all sides up to i form a valid polygon with perimeter prefixSum + nums[i]. Update the answer with this value. Continue scanning because adding more sides may increase the perimeter while still satisfying the constraint.
The greedy insight is that larger perimeters come from using as many sides as possible. Because the array is sorted, the inequality only depends on the current largest side and the cumulative sum before it. Maintaining a running sum eliminates repeated computations and keeps the algorithm linear after sorting.
This approach relies heavily on sorting to order candidate sides and a running sum similar to a prefix sum. The decision step follows a classic greedy strategy: extend the polygon whenever the inequality allows it.
Recommended for interviews: The sorting + greedy prefix sum solution is the expected approach. It demonstrates recognition of the polygon inequality and efficient use of sorted order. Showing the brute force idea first can help explain the constraint, but implementing the optimized version proves you can reduce repeated work and reach the optimal O(n log n) complexity.
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.
In 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.
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.
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.
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.
Time Complexity: O(n^3) due to triple nested loops.
Space Complexity: O(1), apart from input storage no extra space is required.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting and Checking Largest Triangle | 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. |
| Brute Force Approach | Time Complexity: O(n^3) due to triple nested loops. Space Complexity: O(1), apart from input storage no extra space is required. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Recomputed Sums | O(n²) | O(1) | Useful for understanding the polygon inequality and verifying the condition directly |
| Sorting + Greedy Prefix Sum | O(n log n) | O(1) | Best general solution; efficient for large arrays and commonly expected in interviews |
Find Polygon with the Largest Perimeter - Leetcode 2971 - Python • NeetCodeIO • 13,883 views views
Watch 9 more video solutions →Practice Find Polygon With the Largest Perimeter with our built-in code editor and test cases.
Practice on FleetCode