LC-2971 Medium LeetCode

2971. Find Polygon With the Largest Perimeter

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 65% Topics: Array, Greedy, Sorting, Prefix Sum

Reading material

Arrays & Hashing 12 min Greedy 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(1)

# sort, prefix sum, greedy
class Solution(object):
    def largestPerimeter(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        prefix = sum(nums)
        for i in reversed(xrange(2, len(nums))):
            prefix -= nums[i]
            if prefix > nums[i]:
                return prefix+nums[i]
        return -1

Solution from kamyu104/LeetCode-Solutions · MIT