Largest Perimeter Triangle
Problem
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.
nums = [3, 6, 2, 3]8def largest_perimeter(nums):
nums.sort(reverse=True)
for i in range(len(nums) - 2):
a, b, c = nums[i], nums[i + 1], nums[i + 2]
if b + c > a:
return a + b + c
return 0function largestPerimeter(nums) {
nums.sort((x, y) => y - x);
for (let i = 0; i < nums.length - 2; i++) {
const a = nums[i], b = nums[i + 1], c = nums[i + 2];
if (b + c > a) return a + b + c;
}
return 0;
}class Solution {
public int largestPerimeter(int[] nums) {
Arrays.sort(nums);
for (int i = nums.length - 1; i >= 2; i--) {
int a = nums[i], b = nums[i - 1], c = nums[i - 2];
if (b + c > a) return a + b + c;
}
return 0;
}
}int largestPerimeter(vector<int>& nums) {
sort(nums.rbegin(), nums.rend());
for (int i = 0; i + 2 < (int)nums.size(); i++) {
int a = nums[i], b = nums[i + 1], c = nums[i + 2];
if (b + c > a) return a + b + c;
}
return 0;
}Explanation
To make a real triangle from three lengths, the two shorter sides must add up to more than the longest side. That single rule (the triangle inequality) is the whole problem.
Since we want the largest perimeter, it makes sense to try the biggest numbers first. So we sort the array and scan from the largest values downward, looking at three consecutive sides at a time.
Why consecutive? When the values are sorted, the best chance of the inequality holding is when the three sides are as close together in size as possible. If a triplet of neighbors fails, no triplet using that same largest side can succeed, so we just move to the next one.
For each triplet a, b, c (with a the largest), we check if b + c > a. The first time that is true, those three give the biggest valid perimeter, so we return a + b + c.
Example: nums = [3, 6, 2, 3] sorts down to [6, 3, 3, 2]. Try 6, 3, 3: 3 + 3 = 6 is not greater than 6, skip. Try 3, 3, 2: 3 + 2 = 5 > 3, valid, so the answer is 3 + 3 + 2 = 8.