Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/611.html
611. Valid Triangle Number (Medium)
Given an array consists of non-negative integers, your task is to count 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: [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
Note:
- The length of the given array won’t exceed 1000.
- The integers in the given array are in the range of [0, 1000].
Solution 1.
The naive solution is of O(N^3) time complexity, that is, for each triplet, detect if it can form a triangle. This solution will get TLE.
To optimize it, I first sort nums in ascending order. And for each doublet a and b, use binary search to find the count of numbers greater than a + b and less than a - b (a >= b).
// OJ: https://leetcode.com/problems/valid-triangle-number
// Time: O(N^2logN)
// Space: O(1)
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int cnt = 0, N = nums.size();
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
int lb = nums[j] - nums[i], rb = nums[i] + nums[j];
int L = j + 1, R = N - 1, left = 0;
while (L <= R) {
int M = (L + R) / 2;
if (nums[M] > lb) R = M - 1;
else L = M + 1;
}
left = L;
L = j + 1, R = N - 1;
while (L <= R) {
int M = (L + R) / 2;
if (nums[M] >= rb) R = M - 1;
else L = M + 1;
}
if (R >= left) cnt += R - left + 1;
}
}
return cnt;
}
};
Solution 2.
Same as solution 1, just uses built-in functions lower_bound and upper_bound.
// OJ: https://leetcode.com/problems/valid-triangle-number
// Time: O(N^2logN)
// Space: O(1)
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int cnt = 0, N = nums.size();
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
auto left = upper_bound(nums.begin() + j + 1, nums.end(), nums[j] - nums[i]);
auto right = lower_bound(nums.begin() + j + 1, nums.end(), nums[i] + nums[j]);
if (right > left) cnt += right - left;
}
}
return cnt;
}
};
-
class Solution { public int triangleNumber(int[] nums) { int length = nums.length; if (length < 3) return 0; int count = 0; Arrays.sort(nums); int startIndex = 0; while (startIndex < length && nums[startIndex] == 0) startIndex++; int end1 = length - 2; int end2 = length - 1; for (int i = startIndex; i < end1; i++) { int num1 = nums[i]; for (int j = i + 1; j < end2; j++) { int num2 = nums[j]; for (int k = j + 1; k < length; k++) { int num3 = nums[k]; if (num1 + num2 > num3) count++; else break; } } } return count; } } ############ class Solution { public int triangleNumber(int[] nums) { Arrays.sort(nums); int n = nums.length; int res = 0; for (int i = n - 1; i >= 2; --i) { int l = 0, r = i - 1; while (l < r) { if (nums[l] + nums[r] > nums[i]) { res += r - l; --r; } else { ++l; } } } return res; } } -
// OJ: https://leetcode.com/problems/valid-triangle-number // Time: O(N^2logN) // Space: O(1) class Solution { public: int triangleNumber(vector<int>& A) { int N = A.size(), ans = 0; sort(begin(A), end(A)); for (int i = 0; i < N; ++i) { int a = A[i]; for (int j = i + 1; j < N; ++j) { int b = A[j]; auto begin = upper_bound(A.begin() + j + 1, A.end(), b - a); auto end = lower_bound(A.begin() + j + 1, A.end(), a + b); ans += max(0, (int)(end - begin)); } } return ans; } }; -
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 ############ class Solution(object): def triangleNumber(self, nums): ans = 0 nums.sort() for i in range(2, len(nums)): start = 0 end = i - 1 while start < end: if nums[start] + nums[end] > nums[i]: ans += end - start end -= 1 else: start += 1 return ans -
func triangleNumber(nums []int) int { sort.Ints(nums) ans := 0 for i, n := 0, len(nums); i < n-2; i++ { for j := i + 1; j < n-1; j++ { left, right := j+1, n for left < right { mid := (left + right) >> 1 if nums[mid] >= nums[i]+nums[j] { right = mid } else { left = mid + 1 } } ans += left - j - 1 } } return ans } -
function triangleNumber(nums: number[]): number { nums.sort((a, b) => a - b); let n = nums.length; let ans = 0; for (let i = n - 1; i >= 2; i--) { let left = 0, right = i - 1; while (left < right) { if (nums[left] + nums[right] > nums[i]) { ans += right - left; right--; } else { left++; } } } return ans; } -
impl Solution { pub fn triangle_number(mut nums: Vec<i32>) -> i32 { nums.sort(); let n = nums.len(); let mut res = 0; for i in (2..n).rev() { let mut left = 0; let mut right = i - 1; while left < right { if nums[left] + nums[right] > nums[i] { res += right - left; right -= 1; } else { left += 1; } } } res as i32 } }