Problem of The Day: Find Polygon With the Largest Perimeter

Problem Statement

My note:

Intuition

The intuition here is that for a triangle with sides a, b, and c, the sum of any two sides must be greater than the third side. Therefore, to maximize the perimeter, we should try to select the three largest elements from the list.

Approach

My approach is to sort the given list in ascending order. After sorting, I iterate through the list and check if the sum of the two smaller elements is greater than the third, larger element. If it is, I update the answer with the maximum perimeter found so far. This is done until we have considered all possible combinations of three elements.

Complexity

• Time complexity: O(n log n) due to sorting

• Space complexity: O(1)

Code

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        nums.sort()
        N = len(nums)
        curr_sum = 0
        ans = -1
        for i, num in enumerate(nums):
            if i >= 2 and curr_sum > num:
                ans = curr_sum + num
            curr_sum += num

        return ans