Largest Perimeter Triangle — LeetCode 976 Python Solution

The problem

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Example

Input

nums = [2,1,2]

Output

5

Explanation

You can form a triangle with three side lengths: 1, 2, and 2.

Python solution

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums) - 1, 1, -1):
            if (c := nums[i - 1] + nums[i - 2]) > nums[i]:
                return c + nums[i]
        return 0

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 976. Largest Perimeter Triangle is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems