Skip to content

611. Valid Triangle Number

Description

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

 

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

Input: nums = [4,2,3,4]
Output: 4

 

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Solutions

A valid triangle must satisfy: the sum of any two sides is greater than the third side. That is:

\[a + b \gt c \tag{1}\]
\[a + c \gt b \tag{2}\]
\[b + c \gt a \tag{3}\]

If we arrange the sides in ascending order, i.e., \(a \leq b \leq c\), then obviously conditions (2) and (3) are satisfied. We only need to ensure that condition (1) is also satisfied to form a valid triangle.

We enumerate \(i\) in the range \([0, n - 3]\), enumerate \(j\) in the range \([i + 1, n - 2]\), and perform binary search in the range \([j + 1, n - 1]\) to find the first index \(left\) that is greater than or equal to \(nums[i] + nums[j]\). Then, the values of \(k\) in the range \([j + 1, left - 1]\) satisfy the condition, and we add them to the result \(\textit{ans}\).

The time complexity is \(O(n^2\log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the length of the array.

1
2
3
4
5
6
7
8
9
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        ans, n = 0, len(nums)
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                k = bisect_left(nums, nums[i] + nums[j], lo=j + 1) - 1
                ans += k - j
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0, n = nums.length; i < n - 2; ++i) {
            for (int j = i + 1; j < n - 1; ++j) {
                int left = j + 1, right = n;
                while (left < right) {
                    int mid = (left + right) >> 1;
                    if (nums[mid] >= nums[i] + nums[j]) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                ans += left - j - 1;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        ranges::sort(nums);
        int ans = 0, n = nums.size();
        for (int i = 0; i < n - 2; ++i) {
            for (int j = i + 1; j < n - 1; ++j) {
                int sum = nums[i] + nums[j];
                auto it = ranges::lower_bound(nums.begin() + j + 1, nums.end(), sum);
                int k = int(it - nums.begin()) - 1;
                ans += max(0, k - j);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func triangleNumber(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    ans := 0
    for i := 0; i < n-2; i++ {
        for j := i + 1; j < n-1; j++ {
            sum := nums[i] + nums[j]
            k := sort.SearchInts(nums[j+1:], sum) + j + 1 - 1
            if k > j {
                ans += k - j
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function triangleNumber(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            const sum = nums[i] + nums[j];
            let k = _.sortedIndex(nums, sum, j + 1) - 1;
            if (k > j) {
                ans += k - j;
            }
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
impl Solution {
    pub fn triangle_number(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let n = nums.len();
        let mut ans = 0;
        for i in 0..n.saturating_sub(2) {
            for j in i + 1..n.saturating_sub(1) {
                let sum = nums[i] + nums[j];
                let mut left = j + 1;
                let mut right = n;
                while left < right {
                    let mid = (left + right) / 2;
                    if nums[mid] < sum {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                if left > j + 1 {
                    ans += (left - 1 - j) as i32;
                }
            }
        }
        ans
    }
}

Comments