2971. Find Polygon with the Largest Perimeter - Explanation

1. Brute Force

Intuition

A valid polygon requires that the longest side be strictly smaller than the sum of all other sides. We can try each element as the largest side and check if this condition holds. For each candidate, we sum all elements that are less than or equal to it (excluding itself) and verify whether that sum exceeds the candidate. If it does, we have a valid polygon and can compute its perimeter.

Algorithm

Initialize res = -1 to track the maximum perimeter found.
For each element nums[i], treat it as the potential largest side.
Sum all other elements nums[j] where nums[j] <= nums[i].
If the sum of smaller sides exceeds nums[i], update res with the total perimeter.
Return res after checking all possibilities.

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        n = len(nums)
        res = -1

        for i, large in enumerate(nums):
            cur = 0
            for j, side in enumerate(nums):
                if i != j and side <= large:
                    cur += side
            if cur > large:
                res = max(res, cur + large)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

2. Sorting

Intuition

If we sort the array, we can efficiently check the polygon condition. After sorting, as we iterate through each element, all previous elements are smaller or equal. The key insight is that if the running sum of all previous elements exceeds the current element, we have a valid polygon. Since we want the largest perimeter, we keep updating our answer as we find valid configurations, and the last valid one will be the largest.

Algorithm

Sort the array in ascending order.
Initialize res = -1 and total = 0 for the running sum.
Iterate through each number:
- If total > num, we have a valid polygon. Update res = total + num.
- Add num to total.
Return res.

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        res = -1
        total = 0
        for num in nums:
            if total > num:
                res = total + num
            total += num
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

3. Max Heap

Intuition

Instead of sorting, we can use a max heap to process elements from largest to smallest. We start with the total sum and repeatedly extract the maximum element. If the remaining sum (after removing the max) is greater than the max element, we found the largest valid polygon. Otherwise, we subtract that element from our total and try the next largest. This approach can be faster in practice since we often find the answer before processing all elements.

Algorithm

Build a max heap from all elements and compute the total sum.
While the heap has more than 2 elements:
- Extract the largest element.
- Subtract it from the total.
- If largest < total, return total + largest as the perimeter.
If no valid polygon is found, return -1.

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums = [-num for num in nums]
        heapq.heapify(nums)
        total = -sum(nums)

        while len(nums) > 2:
            largest = -heapq.heappop(nums)
            total -= largest
            if largest < total:
                return total + largest
        return -1

Time & Space Complexity

Time complexity:
- $O(n + (30\log n))$ in Python, C++, JS.
- $O(n \log n)$ in Java.
Space complexity: $O(n)$

Common Pitfalls

Using Greater-Than-or-Equal Instead of Strictly Greater

The polygon inequality requires that the longest side be strictly less than the sum of all other sides (equivalently, the sum of other sides must be strictly greater than the longest side). Using >= instead of > in the comparison will incorrectly accept degenerate cases where the sides form a straight line, not a valid polygon.

Integer Overflow with Large Sums

The array can contain up to 10^5 elements, each up to 10^9. The sum of all elements can exceed the 32-bit integer range. Use 64-bit integers (long in Java, long long in C++) for the running total and result to prevent overflow and incorrect comparisons.

Forgetting That Polygons Need At Least 3 Sides

A valid polygon requires at least 3 sides. When iterating through the sorted array, you cannot form a valid polygon until you have accumulated at least 2 previous elements. Starting the validity check too early (e.g., at index 0 or 1) can lead to incorrect results or accessing invalid indices.