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

submission

impl Solution {
    // assume the length of the 3 edges are: a, b, c and 
    // a >= b >= c, to construct a valid triangle, we must
    // have: a < b + c
    // sort the array in descending order, to search for 
    // the largest perimeter triangle, we can just search
    // with a sliding window of size 3, and choose the first
    // window that can construct a valid triangle.
    // we could also solve this with binary heap, which have
    // O(N) time complexity in best case. (O(NlogN) worst case)
    // apparently construct a binary heap from a vec can be done
    // in-place and in O(N) time
    pub fn largest_perimeter(mut nums: Vec<i32>) -> i32 {
        nums.sort_unstable_by(|l, r| r.cmp(l));
        nums.windows(3).find(|w| w[0] < w[1] + w[2]).map_or(0, |w| w.iter().sum())
    }
}