Leetcode 0976. Largest Perimeter Triangle

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`.

Programming Skills I Easy

Description

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 1:

Input: nums = [2,1,2]
Output: 5

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

Example 2:

Input: nums = [1,2,1,10]
Output: 0

• You cannot use the side lengths 1, 1, and 2 to form a triangle.
  You cannot use the side lengths 1, 1, and 10 to form a triangle.
  You cannot use the side lengths 1, 2, and 10 to form a triangle.
  As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

Constraints:

• 3 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^6

Solution

class Solution:
    # Iteration
    # Time Complexity: BigO(N)
    # Space Complexity: BigO(1)
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        for i in range(len(nums)-2):
            if nums[i]<nums[i+1]+nums[i+2]:
                return nums[i]+nums[i+1]+nums[i+2]
        return 0

/**
 * Iteration
 * Time Complexity: BigO(N)
 * Space Complexity: BigO(1)
 */
function largestPerimeter(nums: number[]): number {
  let desc = nums.sort((a, b) => b - a);
  for (let i = 0; i < desc.length; i++) {
    if (desc[i] < desc[i + 1] + desc[i + 2]) {
      return desc[i] + desc[i + 1] + desc[i + 2];
    }
  }
  return 0;
}