Problem Description

You are given an array of positive integers nums of length n. Your task is to find the largest possible perimeter of a polygon that can be formed using some or all of the numbers from the array as side lengths.

A polygon must have at least 3 sides, and for any valid polygon, the longest side must be strictly smaller than the sum of all other sides. This is known as the polygon inequality condition.

The problem states an important property: if you have k positive numbers (where k ≥ 3) arranged in non-decreasing order as a₁ ≤ a₂ ≤ a₃ ≤ ... ≤ aₖ, and if the sum of the first k-1 numbers is greater than the last number (a₁ + a₂ + ... + aₖ₋₁ > aₖ), then you can always form a valid polygon with these k sides.

The perimeter of a polygon is simply the sum of all its side lengths.

Your goal is to:

• Select sides from the given array to form a valid polygon
• Maximize the perimeter of this polygon
• Return the maximum perimeter, or -1 if no valid polygon can be formed

For example:

• If nums = [1, 2, 3, 4, 5], you can form a polygon with sides [2, 3, 4, 5] since 2 + 3 + 4 = 9 > 5, giving a perimeter of 14
• If nums = [1, 2, 10], no valid polygon can be formed since 1 + 2 = 3 is not greater than 10, so return -1

Intuition

To maximize the perimeter, we want to include as many sides as possible with the largest values. The key insight is that if we can form a valid polygon with k sides, we should check if we can form one with k+1 sides by adding another side, as this would give us a larger perimeter.

Let's think about when a set of sides can form a valid polygon. According to the problem, if we have sides in sorted order a₁ ≤ a₂ ≤ ... ≤ aₖ, we need a₁ + a₂ + ... + aₖ₋₁ > aₖ. This means the sum of all smaller sides must exceed the largest side.

This suggests a greedy approach: sort the array first. Why? Because:

1. We can easily identify the largest side in any subset (it's the last element)
2. We can efficiently check the polygon inequality condition
3. We can systematically try different polygon sizes

Once sorted, we can try forming polygons of increasing sizes. For a polygon with k sides using the first k elements of the sorted array, we check if sum(first k-1 elements) > kth element. If this condition holds, we have a valid polygon with perimeter equal to the sum of all k elements.

The beauty of this approach is that we can use prefix sums to efficiently calculate the sum of any subset. By maintaining a running sum as we iterate through possible polygon sizes, we avoid recalculating sums repeatedly.

We start checking from size 3 (minimum polygon size) and go up to n (using all elements). Each time we find a valid polygon, we update our answer with its perimeter if it's larger than what we've found so far. This ensures we find the maximum possible perimeter.

Learn more about Greedy, Prefix Sum and Sorting patterns.

Solution Approach

The solution implements the greedy approach with prefix sums for efficiency:

1. Sort the array: First, we sort nums in ascending order. This allows us to easily identify the largest side in any subset and check the polygon inequality.

2. Build prefix sum array: We create a prefix sum array s using accumulate(nums, initial=0). This gives us:

   • s[0] = 0
   • s[1] = nums[0]
   • s[2] = nums[0] + nums[1]
   • s[k] = nums[0] + nums[1] + ... + nums[k-1]

   This allows us to get the sum of the first k elements in O(1) time.

3. Check all possible polygon sizes: We iterate through all possible polygon sizes from k = 3 to k = len(nums):

   • For each size k, we consider using the first k elements of the sorted array
   • The largest side would be nums[k-1] (the last element in our subset)
   • The sum of all other sides would be s[k-1] (sum of first k-1 elements)

4. Validate polygon inequality: For each size k, we check if s[k-1] > nums[k-1]:

   • If true, we have a valid polygon with perimeter s[k] (sum of all k elements)
   • We update our answer with max(ans, s[k]) to keep track of the maximum perimeter

5. Return result: After checking all possible sizes, we return the maximum perimeter found, or -1 if no valid polygon exists.

The algorithm runs in O(n log n) time due to sorting, with O(n) space for the prefix sum array. The key optimization is using prefix sums to avoid recalculating sums, making each validation check O(1) instead of O(k).

Example Walkthrough

Let's walk through the solution with nums = [3, 6, 2, 3].

Step 1: Sort the array

• Original: [3, 6, 2, 3]
• Sorted: [2, 3, 3, 6]

Step 2: Build prefix sum array

• s[0] = 0
• s[1] = 2
• s[2] = 2 + 3 = 5
• s[3] = 2 + 3 + 3 = 8
• s[4] = 2 + 3 + 3 + 6 = 14

So s = [0, 2, 5, 8, 14]

Step 3: Check all possible polygon sizes

Size k = 3 (using first 3 elements: [2, 3, 3])

• Largest side: nums[2] = 3
• Sum of other sides: s[2] = 5
• Check: Is 5 > 3? YES ✓
• Valid polygon with perimeter = s[3] = 8
• Update answer: ans = 8

Size k = 4 (using all 4 elements: [2, 3, 3, 6])

• Largest side: nums[3] = 6
• Sum of other sides: s[3] = 8
• Check: Is 8 > 6? YES ✓
• Valid polygon with perimeter = s[4] = 14
• Update answer: ans = 14

Step 4: Return result

• Maximum perimeter found: 14

The algorithm correctly identifies that we can form a quadrilateral with all four sides [2, 3, 3, 6], giving us the maximum possible perimeter of 14. Note how the prefix sum array allows us to quickly check the polygon inequality (sum of smaller sides > largest side) in constant time for each potential polygon size.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the length of the input array nums.

• Sorting the array takes O(n log n) time
• Creating the prefix sum array using accumulate takes O(n) time
• The for loop iterates from index 3 to n, which is O(n) iterations
• Each iteration performs constant time operations (comparison and max update)
• Overall: O(n log n) + O(n) + O(n) = O(n log n)

Space Complexity: O(n) where n is the length of the input array.

• The sorting operation may use O(log n) to O(n) space depending on the implementation (Python's Timsort uses up to O(n) in worst case)
• The prefix sum list s stores n+1 elements, requiring O(n) space
• The variable ans uses O(1) space
• Overall: O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Polygon Validation Logic

Pitfall: A common mistake is checking if the longest side is greater than or equal to the sum of other sides, rather than checking if the sum of other sides is strictly greater than the longest side.

# WRONG: This reverses the inequality
if nums[k - 1] >= prefix_sums[k - 1]:  # Incorrect condition
    max_perimeter = max(max_perimeter, prefix_sums[k])

Solution: Always ensure the sum of smaller sides is strictly greater than the longest side:

# CORRECT: Sum of smaller sides must be greater than longest side
if prefix_sums[k - 1] > nums[k - 1]:
    max_perimeter = max(max_perimeter, prefix_sums[k])

2. Forgetting to Sort the Array

Pitfall: Processing the array without sorting it first, which breaks the algorithm's assumption that we can identify the largest side easily.

# WRONG: Operating on unsorted array
def largestPerimeter(self, nums: List[int]) -> int:
    # Missing nums.sort()
    prefix_sums = list(accumulate(nums, initial=0))
    # ... rest of code

Solution: Always sort the array first to ensure elements are in non-decreasing order:

# CORRECT: Sort before processing
nums.sort()
prefix_sums = list(accumulate(nums, initial=0))

3. Off-by-One Errors in Prefix Sum Indexing

Pitfall: Confusing the indexing of prefix sums, especially forgetting that prefix_sums[i] contains the sum of the first i elements (not including index i).

# WRONG: Incorrect indexing
if prefix_sums[k] > nums[k]:  # Off-by-one error
    max_perimeter = prefix_sums[k + 1]  # Another off-by-one error

Solution: Remember that with initial=0, prefix_sums[k] contains the sum of nums[0] through nums[k-1]:

# CORRECT: Proper indexing
if prefix_sums[k - 1] > nums[k - 1]:  # Sum of first k-1 elements > k-th element
    max_perimeter = max(max_perimeter, prefix_sums[k])  # Total sum of k elements

4. Starting Loop from Wrong Index

Pitfall: Starting the loop from k = 2 or k = 1 instead of k = 3, forgetting that a polygon needs at least 3 sides.

# WRONG: Polygon needs at least 3 sides
for k in range(2, len(nums) + 1):  # Starting from 2 is incorrect
    # ...

Solution: Always start from k = 3 since that's the minimum number of sides for a polygon:

# CORRECT: Start from 3 sides minimum
for k in range(3, len(nums) + 1):
    # ...

5. Not Handling Edge Cases

Pitfall: Not considering arrays with fewer than 3 elements, which cannot form any polygon.

Solution: The current implementation handles this naturally since the loop won't execute if len(nums) < 3, returning -1 as expected. However, you could add an explicit check for clarity:

if len(nums) < 3:
    return -1