Leetcode 0976. Largest Perimeter Triangle

Problem statement

https://leetcode.com/problems/largest-perimeter-triangle/

Solution

The optimal triangle can be reached if we use 3 consecutive lengths in sorted array. For each such triple, check if we can create triangle.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def largestPerimeter(self, A):
        A, n, ans = sorted(A), len(A), 0
        for i in range(n - 2):
            if A[i] + A[i+1] > A[i+2]:
                ans = max(ans, sum(A[i:i+3]))
        return ans