Valid Triangle Number
Medium · Two Pointers · Explanation and code example
Sorting and Two-Pointer Triangle Counting
How it works
After sorting nonnegative lengths, only the sum of the two smaller sides needs checking against the largest. Fix the largest index; if the current smaller pair exceeds it, every larger left choice up to the right pointer also works. Count those pairs together.
Steps
- Sort and choose each possible largest side.
- Scan the smaller prefix with two pointers.
- Add right - left when the inequality holds and move right; otherwise advance left.
Complexity
- Time: O(n²).
- Space: Python O(n) worst-case sorting workspace; C++ O(log n) sorting stack.
Things to watch for
- The inequality is strict; degenerate triangles do not count.
- Zero sides fail naturally.
- Count index triplets, including equal lengths at different positions.
Python code example
class Solution:
def triangleNumber(self, nums: list[int]) -> int:
ans = 0
nums.sort()
for k in range(len(nums) - 1, 1, -1):
i = 0
j = k - 1
while i < j:
if nums[i] + nums[j] > nums[k]:
ans += j - i
j -= 1
else:
i += 1
return ans
C++ code example
class Solution {
public:
int triangleNumber(vector<int>& nums) {
if (nums.size() < 3)
return 0;
int ans = 0;
ranges::sort(nums);
for (int k = nums.size() - 1; k > 1; --k) {
int i = 0;
int j = k - 1;
while (i < j)
if (nums[i] + nums[j] > nums[k]) {
// (nums[i], nums[j], nums[k])
// (nums[i + 1], nums[j], nums[k])
// ...
// (nums[j - 1], nums[j], nums[k])
ans += j - i;
--j;
} else {
++i;
}
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.