2971. Find Polygon with the Largest Perimeter - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Arranging elements to efficiently identify the largest side and compare sums
Prefix Sum - Maintaining running totals to quickly compute the sum of smaller sides
Polygon Inequality - Understanding that the longest side must be strictly less than the sum of all other sides

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

public class Solution {
    public long largestPerimeter(int[] nums) {
        int n = nums.length;
        long res = -1;

        for (int i = 0; i < n; i++) {
            int large = nums[i];
            long cur = 0;

            for (int j = 0; j < n; j++) {
                if (i != j && nums[j] <= large) {
                    cur += nums[j];
                }
            }

            if (cur > large) {
                res = Math.max(res, cur + large);
            }
        }

        return res;
    }
}

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        int n = nums.size();
        long long res = -1;

        for (int i = 0; i < n; i++) {
            long long large = nums[i];
            long long cur = 0;

            for (int j = 0; j < n; j++) {
                if (i != j && nums[j] <= large) {
                    cur += nums[j];
                }
            }

            if (cur > large) {
                res = max(res, cur + large);
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    largestPerimeter(nums) {
        const n = nums.length;
        let res = -1;

        for (let i = 0; i < n; i++) {
            const large = nums[i];
            let cur = 0;

            for (let j = 0; j < n; j++) {
                if (i !== j && nums[j] <= large) {
                    cur += nums[j];
                }
            }

            if (cur > large) {
                res = Math.max(res, cur + large);
            }
        }

        return res;
    }
}

public class Solution {
    public long LargestPerimeter(int[] nums) {
        int n = nums.Length;
        long res = -1;

        for (int i = 0; i < n; i++) {
            int large = nums[i];
            long cur = 0;

            for (int j = 0; j < n; j++) {
                if (i != j && nums[j] <= large) {
                    cur += nums[j];
                }
            }

            if (cur > large) {
                res = Math.Max(res, cur + large);
            }
        }

        return res;
    }
}

func largestPerimeter(nums []int) int64 {
    n := len(nums)
    var res int64 = -1

    for i := 0; i < n; i++ {
        large := nums[i]
        var cur int64 = 0

        for j := 0; j < n; j++ {
            if i != j && nums[j] <= large {
                cur += int64(nums[j])
            }
        }

        if cur > int64(large) {
            if cur+int64(large) > res {
                res = cur + int64(large)
            }
        }
    }

    return res
}

class Solution {
    fun largestPerimeter(nums: IntArray): Long {
        val n = nums.size
        var res: Long = -1

        for (i in 0 until n) {
            val large = nums[i]
            var cur: Long = 0

            for (j in 0 until n) {
                if (i != j && nums[j] <= large) {
                    cur += nums[j]
                }
            }

            if (cur > large) {
                res = maxOf(res, cur + large)
            }
        }

        return res
    }
}

class Solution {
    func largestPerimeter(_ nums: [Int]) -> Int {
        let n = nums.count
        var res = -1

        for i in 0..<n {
            let large = nums[i]
            var cur = 0

            for j in 0..<n {
                if i != j && nums[j] <= large {
                    cur += nums[j]
                }
            }

            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

public class Solution {
    public long largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        long res = -1;
        long total = 0;

        for (int num : nums) {
            if (total > num) {
                res = total + num;
            }
            total += num;
        }

        return res;
    }
}

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        long long res = -1;
        long long total = 0;

        for (int& num : nums) {
            if (total > num) {
                res = total + num;
            }
            total += num;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    largestPerimeter(nums) {
        nums.sort((a, b) => a - b);
        let res = -1;
        let total = 0;

        for (let num of nums) {
            if (total > num) {
                res = total + num;
            }
            total += num;
        }

        return res;
    }
}

public class Solution {
    public long LargestPerimeter(int[] nums) {
        Array.Sort(nums);
        long res = -1;
        long total = 0;

        foreach (int num in nums) {
            if (total > num) {
                res = total + num;
            }
            total += num;
        }

        return res;
    }
}

func largestPerimeter(nums []int) int64 {
    sort.Ints(nums)
    var res int64 = -1
    var total int64 = 0

    for _, num := range nums {
        if total > int64(num) {
            res = total + int64(num)
        }
        total += int64(num)
    }

    return res
}

class Solution {
    fun largestPerimeter(nums: IntArray): Long {
        nums.sort()
        var res: Long = -1
        var total: Long = 0

        for (num in nums) {
            if (total > num) {
                res = total + num
            }
            total += num
        }

        return res
    }
}

class Solution {
    func largestPerimeter(_ nums: [Int]) -> Int {
        let sorted = nums.sorted()
        var res = -1
        var total = 0

        for num in sorted {
            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

public class Solution {
    public long largestPerimeter(int[] nums) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        long total = 0;
        for (int num : nums) {
            maxHeap.add(num);
            total += num;
        }

        while (maxHeap.size() > 2) {
            int largest = maxHeap.poll();
            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;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    largestPerimeter(nums) {
        const maxHeap = new MaxPriorityQueue();
        let total = 0;

        nums.forEach((num) => {
            total += num;
            maxHeap.enqueue(num);
        });

        while (maxHeap.size() > 2) {
            const largest = maxHeap.dequeue().element;
            total -= largest;
            if (largest < total) return total + largest;
        }
        return -1;
    }
}

public class Solution {
    public long LargestPerimeter(int[] nums) {
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        long total = 0;

        foreach (int num in nums) {
            maxHeap.Enqueue(num, num);
            total += num;
        }

        while (maxHeap.Count > 2) {
            int largest = maxHeap.Dequeue();
            total -= largest;
            if (largest < total) {
                return total + largest;
            }
        }

        return -1;
    }
}

func largestPerimeter(nums []int) int64 {
    h := &MaxHeap{}
    heap.Init(h)
    var total int64 = 0

    for _, num := range nums {
        heap.Push(h, num)
        total += int64(num)
    }

    for h.Len() > 2 {
        largest := heap.Pop(h).(int)
        total -= int64(largest)
        if int64(largest) < total {
            return total + int64(largest)
        }
    }

    return -1
}

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

class Solution {
    fun largestPerimeter(nums: IntArray): Long {
        val maxHeap = PriorityQueue<Int>(compareByDescending { it })
        var total: Long = 0

        for (num in nums) {
            maxHeap.add(num)
            total += num
        }

        while (maxHeap.size > 2) {
            val largest = maxHeap.poll()
            total -= largest
            if (largest < total) {
                return total + largest
            }
        }

        return -1
    }
}

class Solution {
    func largestPerimeter(_ nums: [Int]) -> Int {
        var heap = Heap<Int>(comparator: >)
        var total = 0

        for num in nums {
            heap.insert(num)
            total += num
        }

        while heap.count > 2 {
            let largest = heap.remove()!
            total -= largest
            if largest < total {
                return total + largest
            }
        }

        return -1
    }
}

struct Heap<T> {
    private var elements: [T] = []
    private let comparator: (T, T) -> Bool

    init(comparator: @escaping (T, T) -> Bool) {
        self.comparator = comparator
    }

    var count: Int { elements.count }

    mutating func insert(_ element: T) {
        elements.append(element)
        siftUp(from: elements.count - 1)
    }

    mutating func remove() -> T? {
        guard !elements.isEmpty else { return nil }
        elements.swapAt(0, elements.count - 1)
        let removed = elements.removeLast()
        if !elements.isEmpty { siftDown(from: 0) }
        return removed
    }

    private mutating func siftUp(from index: Int) {
        var child = index
        var parent = (child - 1) / 2
        while child > 0 && comparator(elements[child], elements[parent]) {
            elements.swapAt(child, parent)
            child = parent
            parent = (child - 1) / 2
        }
    }

    private mutating func siftDown(from index: Int) {
        var parent = index
        while true {
            let left = 2 * parent + 1
            let right = 2 * parent + 2
            var candidate = parent
            if left < elements.count && comparator(elements[left], elements[candidate]) {
                candidate = left
            }
            if right < elements.count && comparator(elements[right], elements[candidate]) {
                candidate = right
            }
            if candidate == parent { return }
            elements.swapAt(parent, candidate)
            parent = candidate
        }
    }
}

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.