Largest Perimeter Triangle

main.md

Question

Approach

I sort the array in nonincreasing order and then scan triples from largest to smallest. For any three sides a >= b >= c, the triangle inequality reduces to a < b + c. So I check consecutive triples in the sorted list; the first triple that satisfies nums[i] < nums[i+1] + nums[i+2] gives the maximum perimeter a + b + c. If no triple works, return 0.

Implementation

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

Complexities

• Time: O(nlogn n)
• Space: O(1)