3Sum Smaller
Medium · Two Pointers · Explanation and code example
Sorting and Two-Pointer Counting
How it works
Fix the first value in a sorted array. If the current left/right pair makes a sum below target, every smaller right index paired with that same left value also works. Count all r - l choices at once, then advance the left pointer.
Steps
- Sort and choose each first index.
- Scan its suffix with left and right pointers.
- Count r - l valid pairs when the sum is small; otherwise move right leftward.
Complexity
- Time: O(n²).
- Space: Python O(n) worst-case sorting workspace; C++ O(log n) sorting stack.
Things to watch for
- Use a strict comparison with target.
- Count index triplets, including repeated values at different positions.
- Return zero for fewer than three values.
Python code example
class Solution:
def threeSumSmaller(self, nums: list[int], target: int) -> int:
if len(nums) < 3:
return 0
ans = 0
nums.sort()
for i in range(len(nums) - 2):
l = i + 1
r = len(nums) - 1
while l < r:
if nums[i] + nums[l] + nums[r] < target:
# (nums[i], nums[l], nums[r])
# (nums[i], nums[l], nums[r - 1])
# ...,
# (nums[i], nums[l], nums[l + 1])
ans += r - l
l += 1
else:
r -= 1
return ans
C++ code example
class Solution {
public:
int threeSumSmaller(vector<int>& nums, int target) {
if (nums.size() < 3)
return 0;
int ans = 0;
ranges::sort(nums);
for (int i = 0; i + 2 < nums.size(); ++i) {
int l = i + 1;
int r = nums.size() - 1;
while (l < r)
if (nums[i] + nums[l] + nums[r] < target) {
// (nums[i], nums[l], nums[r])
// (nums[i], nums[l], nums[r - 1])
// ...,
// (nums[i], nums[l], nums[l + 1])
ans += r - l;
++l;
} else {
--r;
}
}
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.