⚡Flashcard Drill➔
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

  1. 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.
  2. If a sorted array satisfies this for some index i, then using the prefix nums[0..i] maximises the perimeter among all valid subsets ending at i.
  3. So sort the array and scan from the largest index downward: the first index where nums[i] < sum(nums[0..i-1]) gives the answer sum(nums[0..i]).
  4. 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 >= 2 bound: 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems