LeetCode Problem 2971

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Prefix Sum

Solution

LeetCode 2971 - Find Polygon With the Largest Perimeter

Problem Understanding

The problem gives us an array nums containing positive integers. Each integer represents a potential side length that we may use when constructing a polygon.

A polygon must have at least three sides. The key geometric property we are given is that if the side lengths are sorted and the largest side is smaller than the sum of all other sides, then a valid polygon can always be formed. Therefore, for any selected set of sides:

sum(all sides except largest) > largest

must hold.

Our goal is to select some subset of the given numbers, containing at least three elements, such that:

1. The selected sides can form a valid polygon.
2. The perimeter, which is the sum of all selected sides, is as large as possible.

If no valid polygon can be formed, we return -1.

The constraints are important:

• 3 <= n <= 100000
• 1 <= nums[i] <= 1000000000

Since n can be as large as 100,000, any exponential or quadratic solution is far too slow. We need something close to O(n log n).

Several edge cases are worth noticing immediately:

• The array may contain exactly three numbers.
• The largest value may be much larger than all others combined.
• A valid polygon might require discarding some large numbers.
• The answer can exceed 32-bit integer range because there may be up to 100,000 numbers each as large as 10^9, so the perimeter may reach 10^14. We must use 64-bit integers.
• Since all values are positive, adding more sides generally increases perimeter, provided the polygon condition remains valid.

Approaches

Brute Force

A brute-force solution would examine every possible subset of the array that contains at least three elements.

For each subset, we would:

1. Sort the chosen side lengths.
2. Check whether the largest side is smaller than the sum of the remaining sides.
3. If valid, compute the perimeter.
4. Track the maximum perimeter found.

This approach is correct because it explicitly checks every possible polygon that can be formed.

However, there are 2^n possible subsets. Even for n = 50, this becomes completely infeasible. With n = 100000, such an approach is impossible.

Key Insight

First sort the array in ascending order.

Suppose the sorted array is:

a0 <= a1 <= a2 <= ... <= an-1

Let the total sum of the first i + 1 elements be a prefix sum.

Consider using all elements from index 0 through i as the polygon sides. Since the array is sorted, nums[i] is the largest side.

The polygon condition becomes:

prefixSum(i) - nums[i] > nums[i]

or equivalently:

prefixSum(i) > 2 * nums[i]

Now comes the crucial observation.

Because all numbers are positive, if a prefix ending at index i forms a valid polygon, then its perimeter is exactly prefixSum(i).

To maximize perimeter, we should use as many sides as possible. After sorting, we can process prefixes from left to right and record every valid prefix. The largest valid prefix sum encountered will be the answer.

Why does checking prefixes suffice?

Suppose a valid solution uses some subset ending with largest side nums[i]. Adding additional smaller positive sides only increases the left side of the inequality and cannot make the polygon invalid. Therefore, for any largest side nums[i], the maximum perimeter using that largest side is obtained by including all smaller sides. That means every optimal solution corresponds to some sorted prefix.

This reduces the problem to checking each prefix once.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n · n log n)	O(n)	Enumerates every subset
Optimal	O(n log n)	O(1) extra, excluding sort	Sort once and check each prefix

Algorithm Walkthrough

1. Sort nums in non-decreasing order.

Sorting allows us to easily identify the largest side in any candidate polygon and efficiently evaluate the polygon condition. 2. Initialize a running prefix sum.

As we iterate through the sorted array, we maintain the sum of all elements seen so far. 3. Start scanning the sorted array from left to right.

For each index i, add nums[i] to the running sum. 4. Ignore prefixes with fewer than three elements.

A polygon must contain at least three sides, so we only start checking when i >= 2. 5. Check the polygon condition.

Let the current prefix sum be currentSum.

The largest side is nums[i].

The polygon condition is:

currentSum - nums[i] > nums[i]

If this holds, then all sides from index 0 through i form a valid polygon. 6. Update the answer.

When a valid polygon is found, its perimeter is exactly currentSum.

Record the maximum perimeter seen so far. 7. Return the answer.

If no valid prefix was ever found, return -1.

Why it works

After sorting, any polygon whose largest side is nums[i] achieves its maximum possible perimeter by including every smaller side. Since all side lengths are positive, adding extra smaller sides increases the perimeter and makes the inequality easier to satisfy. Therefore every optimal solution corresponds to a prefix of the sorted array. Checking each prefix guarantees that we evaluate every possible optimal candidate, and selecting the largest valid prefix sum yields the maximum perimeter.

Python Solution

from typing import List

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()

        prefix_sum = 0
        answer = -1

        for i, value in enumerate(nums):
            prefix_sum += value

            if i >= 2 and prefix_sum - value > value:
                answer = prefix_sum

        return answer

The implementation begins by sorting the array. This guarantees that the current element is always the largest side in the current prefix.

The variable prefix_sum stores the sum of all elements processed so far. As we iterate through the sorted array, we continuously update this value.

Once at least three elements have been included, we test the polygon condition:

prefix_sum - value > value

where value is the largest side of the current prefix.

Whenever the condition is satisfied, the entire prefix forms a valid polygon. Since prefix_sum is the perimeter of that polygon, we store it as the current answer.

Because we process prefixes in increasing order of size and all values are positive, later valid prefixes have larger perimeters. Storing the latest valid perimeter naturally gives the maximum result.

Go Solution

import "sort"

func largestPerimeter(nums []int) int64 {
	sort.Ints(nums)

	var prefixSum int64
	var answer int64 = -1

	for i, value := range nums {
		prefixSum += int64(value)

		if i >= 2 && prefixSum-int64(value) > int64(value) {
			answer = prefixSum
		}
	}

	return answer
}

The Go solution follows exactly the same logic as the Python version.

The main implementation difference is the use of int64 for both prefixSum and answer. The perimeter can be as large as:

100000 × 1000000000 = 100000000000000

which exceeds 32-bit integer limits. Using int64 prevents overflow.

Worked Examples

Example 1

Input:

[5,5,5]

Sorted array:

[5,5,5]

i	value	prefixSum	Check	Valid?	answer
0	5	5	fewer than 3 sides	No	-1
1	5	10	fewer than 3 sides	No	-1
2	5	15	15 - 5 > 5	Yes	15

Final answer:

15

Example 2

Input:

[1,12,1,2,5,50,3]

Sorted array:

[1,1,2,3,5,12,50]

i	value	prefixSum	Condition	Valid?	answer
0	1	1	N/A	No	-1
1	1	2	N/A	No	-1
2	2	4	2 > 2	No	-1
3	3	7	4 > 3	Yes	7
4	5	12	7 > 5	Yes	12
5	12	24	12 > 12	No	12
6	50	74	24 > 50	No	12

Final answer:

12

Example 3

Input:

[5,5,50]

Sorted array:

[5,5,50]

i	value	prefixSum	Condition	Valid?
0	5	5	N/A	No
1	5	10	N/A	No
2	50	60	10 > 50	No

No valid polygon exists.

Final answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) extra, excluding sort	Only a few variables are maintained

The scan after sorting is linear, requiring only one pass through the array. The sorting step costs O(n log n), which dominates the overall complexity. Aside from the sort implementation itself, the algorithm uses only constant additional memory.

Test Cases

sol = Solution()

assert sol.largestPerimeter([5, 5, 5]) == 15  # example 1

assert sol.largestPerimeter([1, 12, 1, 2, 5, 50, 3]) == 12  # example 2

assert sol.largestPerimeter([5, 5, 50]) == -1  # example 3

assert sol.largestPerimeter([2, 3, 4]) == 9  # simple triangle

assert sol.largestPerimeter([1, 1, 2]) == -1  # degenerate triangle

assert sol.largestPerimeter([1, 1, 2, 3]) == -1  # no valid polygon

assert sol.largestPerimeter([1, 2, 2, 3]) == 8  # valid quadrilateral

assert sol.largestPerimeter([1, 1, 1, 1]) == 4  # all equal sides

assert sol.largestPerimeter([10, 11, 12, 13]) == 46  # entire array valid

assert sol.largestPerimeter([1, 1, 1, 100]) == 3  # discard large outlier

assert sol.largestPerimeter([1000000000, 1000000000, 1000000000]) == 3000000000  # large values

assert sol.largestPerimeter([3, 4, 5, 100]) == 12  # best polygon excludes largest

assert sol.largestPerimeter([2, 2, 3, 4, 10]) == 11  # largest element unusable

assert sol.largestPerimeter([1, 2, 3, 4, 5, 6]) == 21  # large valid prefix

assert sol.largestPerimeter([1, 1, 1]) == 3  # minimum size valid case

Test Summary

Test	Why
[5,5,5]	Provided example, valid polygon
[1,12,1,2,5,50,3]	Provided example, requires excluding large values
[5,5,50]	Provided example, impossible case
[2,3,4]	Basic valid triangle
[1,1,2]	Boundary where equality fails
[1,1,2,3]	No valid polygon despite four numbers
[1,2,2,3]	Valid quadrilateral
[1,1,1,1]	Uniform side lengths
[10,11,12,13]	Entire array forms polygon
[1,1,1,100]	Large outlier must be ignored
Large 10^9 values	Verifies 64-bit perimeter handling
[3,4,5,100]	Optimal answer excludes largest element
[2,2,3,4,10]	Later element breaks validity
[1,2,3,4,5,6]	Large valid prefix
[1,1,1]	Smallest valid input size

Edge Cases

Equality Does Not Count

A common mistake is using >= instead of >.

Consider:

[1,1,2]

The condition becomes:

1 + 1 = 2

A valid polygon requires the sum of the smaller sides to be strictly greater than the largest side. Equality is not sufficient. The implementation correctly uses:

prefix_sum - value > value

which rejects this case.

Very Large Side Lengths

The side lengths may be as large as 10^9, and there may be up to 100000 of them.

The perimeter can therefore reach:

100000 × 10^9 = 10^14

This exceeds the range of a 32-bit integer. The Go solution explicitly uses int64, and Python automatically supports arbitrarily large integers.

The Largest Numbers May Need to Be Excluded

Consider:

[3,4,5,100]

Using all four sides fails because:

3 + 4 + 5 = 12 < 100

However, the first three sides form a valid triangle with perimeter 12.

A naive strategy that only checks the entire array would incorrectly return -1. The prefix-based approach evaluates every possible largest side and therefore correctly finds the best valid perimeter.

No Valid Polygon Exists

Consider:

[1,1,100]

The largest side is much larger than the sum of the others.

Every possible polygon candidate fails the polygon inequality. The answer variable remains -1, and the implementation correctly returns -1 when no valid prefix is found.