2971. Find Polygon with the Largest Perimeter - Explanation

Description

Choose at least three entries of nums as side lengths of a polygon. Such a polygon exists exactly when its longest side is strictly shorter than the sum of all other chosen sides. Return the largest possible sum of chosen side lengths, or -1 if no polygon can be formed.

Example 1:

Input: nums = [2,3,4]

Output: 9

Explanation: Use all three sides. The longest side, 4, is smaller than 2 + 3, so the perimeter is 2 + 3 + 4 = 9.

Example 2:

Input: nums = [1,2,3]

Output: -1

Explanation: The longest side equals 1 + 2, but the inequality must be strict. With only three available entries, no polygon is possible.

Example 3:

Input: nums = [3,3,3,20]

Output: 9

Explanation: The side of length 20 exceeds the sum of the other sides, so it cannot be used. The three sides of length 3 form a polygon with perimeter 9.

Constraints:

3 <= nums.length <= 100000
1 <= nums[i] <= 1000000000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

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
    }
}

impl Solution {
    pub fn largest_perimeter(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut res: i64 = -1;

        for i in 0..n {
            let large = nums[i] as i64;
            let mut cur: i64 = 0;

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

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

        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
    }
}

impl Solution {
    pub fn largest_perimeter(mut nums: Vec<i32>) -> i64 {
        nums.sort();
        let mut res: i64 = -1;
        let mut total: i64 = 0;

        for &num in &nums {
            if total > num as i64 {
                res = total + num as i64;
            }
            total += num as i64;
        }

        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
        }
    }
}

impl Solution {
    pub fn largest_perimeter(nums: Vec<i32>) -> i64 {
        let mut max_heap = BinaryHeap::new();
        let mut total: i64 = 0;

        for &num in &nums {
            max_heap.push(num);
            total += num as i64;
        }

        while max_heap.len() > 2 {
            let largest = max_heap.pop().unwrap() as i64;
            total -= largest;
            if largest < total {
                return total + largest;
            }
        }

        -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.