#2971

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Find Polygon With the Largest Perimeter

Determine the largest perimeter polygon from a set of side lengths using a greedy approach with invariant validation checks.

array greedy sorting prefix sum

Problem Statement

Given an array of positive integers nums of length n, determine the largest perimeter of any polygon that can be formed using these numbers as side lengths. A valid polygon must have at least three sides, and its longest side must be smaller than the sum of the other sides.

If no valid polygon can be formed, return -1. Use the array of side lengths to find a combination that maximizes the perimeter while respecting the polygon inequality, emphasizing a greedy choice approach.

Examples

Example 1

Input: nums = [5,5,5]

Output: 15

The only possible polygon that can be made from nums has 3 sides: 5, 5, and 5. The perimeter is 5 + 5 + 5 = 15.

Example 2

Input: nums = [1,12,1,2,5,50,3]

Output: 12

The polygon with the largest perimeter which can be made from nums has 5 sides: 1, 1, 2, 3, and 5. The perimeter is 1 + 1 + 2 + 3 + 5 = 12. We cannot have a polygon with either 12 or 50 as the longest side because it is not possible to include 2 or more smaller sides that have a greater sum than either of them. It can be shown that the largest possible perimeter is 12.

Example 3

Input: nums = [5,5,50]

Output: -1

There is no possible way to form a polygon from nums, as a polygon has at least 3 sides and 50 > 5 + 5.

Constraints

3 <= n <= 105
1 <= nums[i] <= 109

Solution Approach

Sort the Array

Begin by sorting nums in descending order. Sorting ensures that when checking consecutive triplets, the first valid polygon found will have the largest perimeter, aligning with the greedy choice principle.

Check Triplets for Polygon Validity

Iterate through the sorted array, examining each triplet of consecutive elements. Confirm that the sum of the two smaller sides is greater than the largest side. This invariant guarantees that a valid polygon can be formed.

Return Maximum Perimeter or -1

Once a valid triplet is found, calculate its perimeter and return it immediately. If no triplet satisfies the polygon condition, return -1, reflecting the failure mode when the longest side exceeds the sum of the others.

Complexity Analysis

Metric	Value
Time	O(N\cdot logN)
Space	O(N)

Sorting the array requires O(N\cdot logN) time, and iterating through triplets takes O(N) time, resulting in overall O(N\cdot logN). Space complexity is O(N) if sorting creates a copy.

What Interviewers Usually Probe

Sorting the array suggests a greedy approach for largest perimeter selection.
Examining triplets indicates knowledge of polygon inequalities.
Returning immediately on first valid triplet shows understanding of optimal greedy invariant.

Common Pitfalls or Variants

Common pitfalls

Failing to sort the array may lead to suboptimal perimeter calculation.
Not validating the polygon inequality for the triplet can produce invalid polygons.
Assuming any three sides form a polygon without checking the longest side.

Follow-up variants

Find the polygon with the smallest perimeter instead of the largest, requiring reversed greedy logic.
Determine the number of distinct valid polygons that can be formed from nums.
Compute the largest perimeter for polygons with more than three sides, generalizing triplet checks.

FAQ

What is the main idea behind Find Polygon With the Largest Perimeter?

The key is to sort the array and use a greedy approach to select the largest valid triplet that satisfies the polygon inequality.

Why do we need to sort the array first?

Sorting ensures that the largest sides are considered first, which guarantees that the first valid polygon found will have the maximum perimeter.

What if no valid polygon can be formed?

Return -1, as this indicates that all triplets fail the polygon inequality with the longest side exceeding the sum of the others.

Can this method handle very large arrays?

Yes, sorting and iterating through the array scales with O(N\cdot logN), which is efficient for arrays up to 10^5 elements.

How does the greedy choice plus invariant validation pattern apply here?

By always picking the largest available sides and validating the polygon inequality, you ensure both optimal perimeter and correctness, directly applying the pattern.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        s = list(accumulate(nums, initial=0))
        ans = -1
        for k in range(3, len(nums) + 1):
            if s[k - 1] > nums[k - 1]:
                ans = max(ans, s[k])
        return ans

Continue Practicing

#2587 rearrange array to maximize prefix score #3362 zero array transformation iii #3413 maximum coins from k consecutive bags