MediumNo. 2971
Find Polygon With the Largest Perimeter — LeetCode 2971 Python Solution
- Pattern
- Prefix Sum
- Topics
- Greedy, Array, Prefix Sum, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an array of positive integers nums of length n. A polygon is a closed plane figure that has at least 3 sides.
Example
- Input
- nums = [5,5,5]
- Output
- 15
- Explanation
- The only possible polygon that can be made from nums has 3 sides: 5, 5, and 5. The perimeter is 5 + 5 + 5 = 15.
Python solution
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 ansComplexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 2971. Find Polygon With the Largest Perimeter is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1589 | Maximum Sum Obtained of Any Permutation | Medium |
| 1838 | Frequency of the Most Frequent Element | Medium |
| 2171 | Removing Minimum Number of Magic Beans | Medium |
| 2234 | Maximum Total Beauty of the Gardens | Hard |
| 2271 | Maximum White Tiles Covered by a Carpet | Medium |
| 2406 | Divide Intervals Into Minimum Number of Groups | Medium |
Frequently asked questions
- How hard is LeetCode 2971. Find Polygon With the Largest Perimeter?
LeetCode 2971. Find Polygon With the Largest Perimeter is rated Medium on LeetCode.
- What topics does LeetCode 2971. Find Polygon With the Largest Perimeter cover?
LeetCode 2971. Find Polygon With the Largest Perimeter is tagged Greedy, Array, Prefix Sum and Sorting on LeetCode.