Problem Statement in English

You’re given an integer array nums, where the lengths of the sides of a triangle are represented by the elements in the array.

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.

Approach

We know that the triangle inequality theorem must be satisfied for three sides to form a valid triangle. The theorem states that the sum of the lengths of any two sides must be greater than the length of the third side.

To find the largest perimeter, we can sort the array in non-increasing order and then iterate through the sorted array, checking each triplet of sides. The first valid triplet we find will have the largest perimeter.

Solution in Python


class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort(reverse=True)

        for i in range(len(nums)-2):
            if nums[i + 1] + nums[i + 2] > nums[i]:
                return nums[i + 1] + nums[i + 2] + nums[i]

        return 0

Complexity

  • Time: $O(n \log n)$
    Since we sort the array first, which takes O(n log n) time.

  • Space: $O(1)$
    Since we are sorting the array in place and using only a constant amount of extra space.

And we are done.