Find Polygon With the Largest Perimeter

How it works

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.

Steps

1. Build a max heap from all elements and compute the total sum.
2. 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.
3. If no valid polygon is found, return -1.

Complexity

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

Things to watch for

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.

from typing import List
import heapq

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

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        priority_queue<int> maxHeap(nums.begin(), nums.end());
        long long total = accumulate(nums.begin(), nums.end(), 0LL);

        while (maxHeap.size() > 2) {
            int largest = maxHeap.top();
            maxHeap.pop();
            total -= largest;
            if (largest < total) {
                return total + largest;
            }
        }
        return -1;
    }
};