NeetCode #150LC-2971MediumArrays & Hashing
← Back to All Problems#150 · #2971 · Find Polygon With the Largest Perimeter(找到最大周长的多边形)
📌 Problem Statement & Constraints
Given an array
nums of positive integers, return the largest perimeter of a polygon with at least 3 sides that can be formed from a subset of nums, or -1 if impossible. Constraints: 3 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9.💡 Core Algorithmic Approaches
- The polygon inequality for a sorted set of side lengths is that the largest side must be strictly less than the sum of the others.
- If a sorted array satisfies this for some index
i, then using the prefixnums[0..i]maximises the perimeter among all valid subsets ending ati. - So sort the array and scan from the largest index downward: the first index where
nums[i] < sum(nums[0..i-1])gives the answersum(nums[0..i]). - Scanning from the largest index guarantees the maximum perimeter, since the perimeter is the prefix sum.
💻 Benchmark Python3 Implementation
class Solution:
def largestPerimeter(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
pref = [0] * (n + 1)
for i, x in enumerate(nums):
pref[i + 1] = pref[i] + x
for i in range(n - 1, 1, -1): # at least 3 sides
if nums[i] < pref[i]: # largest < sum of the rest
return pref[i + 1]
return -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates; the scan is O(n).
💾 Space Complexity
O(n) for the prefix array (O(1) extra with a running total).
⚠️ Interview Pitfalls & Follow-ups
- Using
<=instead of<: the polygon inequality is strict; a degenerate triangle where the largest equals the sum of the others has zero area and is invalid. - Requiring exactly 3 sides: the problem allows any number of sides, so a longer prefix may give a larger perimeter.
- Scanning from the smallest index: that would return the smallest valid perimeter, not the largest.
- Forgetting the
i >= 2bound: a polygon needs at least 3 sides.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.