Valid Triangle Number
Problem
Count triples (i, j, k) where the three values form a triangle.
nums = [2,2,3,4]3def triangle_number(nums):
nums = sorted(nums); cnt = 0
for k in range(len(nums) - 1, 1, -1):
i, j = 0, k - 1
while i < j:
if nums[i] + nums[j] > nums[k]: cnt += j - i; j -= 1
else: i += 1
return cntfunction triangleNumber(nums) {
nums.sort((a, b) => a - b); let cnt = 0;
for (let k = nums.length - 1; k >= 2; k--) {
let i = 0, j = k - 1;
while (i < j) {
if (nums[i] + nums[j] > nums[k]) { cnt += j - i; j--; }
else i++;
}
}
return cnt;
}int triangleNumber(int[] nums) {
Arrays.sort(nums); int cnt = 0;
for (int k = nums.length - 1; k >= 2; k--) {
int i = 0, j = k - 1;
while (i < j) {
if (nums[i] + nums[j] > nums[k]) { cnt += j - i; j--; }
else i++;
}
}
return cnt;
}int triangleNumber(vector& nums) {
sort(nums.begin(), nums.end()); int cnt = 0;
for (int k = nums.size() - 1; k >= 2; k--) {
int i = 0, j = k - 1;
while (i < j) {
if (nums[i] + nums[j] > nums[k]) { cnt += j - i; j--; }
else i++;
}
}
return cnt;
} Explanation
Three lengths form a triangle when the two shorter sides add up to more than the longest side. The trick that makes this fast is to sort the array first — once values are in order, we can fix the longest side and count valid pairs with two pointers instead of checking every triple.
We loop k from the largest value down. Treating nums[k] as the longest side, we set i = 0 and j = k - 1 and look at the pair nums[i] + nums[j].
If nums[i] + nums[j] > nums[k], then this j works — and because the array is sorted, every index between i and j also works with that same j. So we add j - i at once and then shrink the window with j--. If the sum is too small, the only way to grow it is i++ to pick a bigger small side.
Example: nums = [2, 2, 3, 4] (already sorted). Fix k=3 (value 4): 2 + 3 = 5 > 4, so add j - i = 2 pairs, then j--; next 2 + 2 = 4 is not greater, so i++. Fix k=2 (value 3): 2 + 2 = 4 > 3, add 1 more. Total count is 3.
The outer loop over k times the inner two-pointer sweep gives an overall O(n²) — far better than checking all triples one by one.