Find Polygon With the Largest Perimeter - Solution & Explanation
Problem Statement
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] <= 109
Approach Overview
Problem 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.
Approach 1: Sorting and Checking Largest Triangle
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.
Complexity
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.
Approach 2: Brute Force Approach
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.
Complexity
Time Complexity: O(n^3) due to triple nested loops.
Space Complexity: O(1), apart from input storage no extra space is required.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | ā |
Detailed Complexity Analysis
| 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 |
Video Solution
Find Polygon with the Largest Perimeter - Leetcode 2971 - Python ā¢ NeetCodeIO ā¢ 13,961 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Find Polygon With the Largest Perimeter easy or hard?
Find Polygon With the Largest Perimeter Python/Java solution
How to solve Find Polygon With the Largest Perimeter in O(n)?
What is the best approach for Find Polygon With the Largest Perimeter?
Is Find Polygon With the Largest Perimeter asked at Google/Amazon/Meta?
What data structure is used in Find Polygon With the Largest Perimeter?
What is the time complexity of Find Polygon With the Largest Perimeter?
Ready to solve this problem?
Practice Find Polygon With the Largest Perimeter with our built-in code editor and test cases.
Practice on FleetCode