Skip to content

976. Largest Perimeter Triangle

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
Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

Example 2:

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
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 <= 104
  • 1 <= nums[i] <= 106

Solutions

Solution 1: Sorting + Greedy

Thinking

Sides \(a\le b\le c\) form a triangle iff \(a+b>c\), and we want the largest perimeter. All triples are cubic. After sorting, try \(c\) from large to small with the two neighboring sides; the first triple that satisfies the inequality is optimal, otherwise that \(c\) cannot work.

Suppose the three sides of the triangle are \(a \leq b \leq c\). The triangle has non-zero area if and only if \(a + b \gt c\).

We can enumerate the largest side \(c\), then select the two largest remaining sides \(a\) and \(b\). If \(a + b \gt c\), a triangle with non-zero area can be formed, and its perimeter will be the largest possible; otherwise, continue to enumerate the next largest side \(c\).

The time complexity is \(O(n \log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
7
class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums) - 1, 1, -1):
            if (c := nums[i - 1] + nums[i - 2]) > nums[i]:
                return c + nums[i]
        return 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 2; --i) {
            int c = nums[i - 1] + nums[i - 2];
            if (c > nums[i]) {
                return c + nums[i];
            }
        }
        return 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        ranges::sort(nums);
        for (int i = nums.size() - 1; i > 1; --i) {
            int c = nums[i - 1] + nums[i - 2];
            if (c > nums[i]) {
                return c + nums[i];
            }
        }
        return 0;
    }
};

1
2
3
4
5
6
7
8
9
func largestPerimeter(nums []int) int {
    sort.Ints(nums)
    for i := len(nums) - 1; i >= 2; i-- {
        if c := nums[i-1] + nums[i-2]; c > nums[i] {
            return c + nums[i]
        }
    }
    return 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function largestPerimeter(nums: number[]): number {
    nums.sort((a, b) => a - b);
    for (let i = nums.length - 1; i > 1; --i) {
        const [a, b, c] = nums.slice(i - 2, i + 1);
        if (a + b > c) {
            return a + b + c;
        }
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn largest_perimeter(mut nums: Vec<i32>) -> i32 {
        let n = nums.len();
        nums.sort_unstable_by(|a, b| b.cmp(&a));
        for i in 2..n {
            let (a, b, c) = (nums[i - 2], nums[i - 1], nums[i]);
            if a < b + c {
                return a + b + c;
            }
        }
        0
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int cmp(const void* a, const void* b) {
    return *(int*) b - *(int*) a;
}

int largestPerimeter(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 2; i < numsSize; i++) {
        if (nums[i - 2] < nums[i - 1] + nums[i]) {
            return nums[i - 2] + nums[i - 1] + nums[i];
        }
    }
    return 0;
}

Comments