Two Pointers — 3Sum Smaller
↗ LeetCode: 3Sum Smaller · Medium · pattern chapter →
Asked atGoogleAmazon
Count triplets (i, j, k) with i < j < k and nums[i] + nums[j] + nums[k] < target.
Example 1 — nums=[-2,0,1,3], target=2 → 2Example 2 — nums=[], target=0 → 0
Constraints — 0 ≤ n ≤ 3500. Brute is O(n³) ≈ 4·10¹⁰ ops at n=3500 (TLE). Sort + two-pointer with count is O(n²) ≈ 1.2·10⁷ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Triple loop
O(n³).
Approach 2 — Sort + counting two-pointer (canonical)
Insight. After sorting, for each i and left pointer l, if nums[i]+nums[l]+nums[r] < target, then every k in (l, r] also satisfies it — add r - l.
java
int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int count = 0;
for (int i = 0; i < nums.length - 2; i++) {
int l = i + 1, r = nums.length - 1;
while (l < r) {
if (nums[i] + nums[l] + nums[r] < target) { count += r - l; l++; }
else r--;
}
}
return count;
}Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(n²); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Triple loop | O(n³) | O(1) | baseline |
| Sort + counting | O(n²) | O(1) | canonical |
When to use which
- "Count triplets < target" → sort + counting shortcut.
- "Return the triplets" → enumerate; loses O(1).
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems