Published: Oct 20, 2022
This problem requires a bit of trigonometry knowledge. To form a triangle, 3 sides a, b, c should have the length, a + b > c, where c is the longest side. Sort the given array, then find 3 largest values which satisfy the condition.
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.
3 <= nums.length <= 10**4
1 <= nums[i] <= 10**6
Example 1 Input: nums = [2,1,2] Output: 5
Example 2 Input: nums = [1,2,1] Output: 0
The first step is to sort the given array.
The examples show an array of just 3 elements, but as in the constraints, the array is much longer.
To find 3 sides, shift 3 values one by one.
This is because
a + b > c is a condition.
If the current longest doesn’t satisfy the condition, the longest should be switched to the next longest.
Without changing the longest c, changing a or b might work.
However, a + b + c must be the largest. So, shifting values one by one gives us the answer.
class LargestPerimeterTriangle: def largestPerimeter(self, nums: List[int]) -> int: nums.sort() for i in range(len(nums) - 3, -1, -1): if nums[i] + nums[i + 1] > nums[i + 2]: return nums[i] + nums[i + 1] + nums[i + 2] return 0