Two Pointers — 3Sum Closest
↗ LeetCode: 3Sum Closest · Medium · pattern chapter →
Given an integer array nums of length n and integer target, return the sum of three integers from nums that is closest to target.
Example 1 — nums = [-1,2,1,-4], target = 1 → 2 (-1 + 2 + 1 = 2) Example 2 — nums = [0,0,0], target = 1 → 0Example 3 — nums = [1,1,1,0], target = -100 → 2
Constraints — 3 ≤ n ≤ 500; -10³ ≤ nums[i], target ≤ 10³. Brute enumerates every triple in O(n³) = 1.25·10⁸ ops at n=500 (borderline). Sort + two-pointer is O(n²) = 2.5·10⁵ ops.
Interview timer00:00
Approach 1 — Triple nested loop
Intuition. Enumerate every triplet; keep the sum with smallest |sum - target|.
int threeSumClosestBrute(int[] nums, int target) {
int n = nums.length, best = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++) {
int s = nums[i] + nums[j] + nums[k];
if (Math.abs(s - target) < Math.abs(best - target)) best = s;
}
return best;
}Complexity — Time O(n³); Space O(1).
Approach 2 — Sort + two-pointer
Insight from brute. Same shape as 3Sum. Sort. Fix i; two pointers on [i+1, n-1] — move whichever pointer nudges the sum toward target.
Early return. If sum exactly equals target, we can't beat it.
int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n - 2; i++) {
int l = i + 1, r = n - 1;
while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (Math.abs(s - target) < Math.abs(best - target)) best = s;
if (s == target) return s;
if (s < target) l++;
else r--;
}
}
return best;
}Complexity — Time O(n²); Space O(1) extra.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Triple loop | O(n³) | O(1) | baseline |
| Sort + two-pointer | O(n²) | O(1) | expected optimum |
When to use which
- First pass — sort + two-pointer.
- "Return triplet, not sum" → track
(a, b, c)alongsidebest. - "kSum closest" → recurse: fix (k-2) values, close with 2-pointer.
- Skip duplicates — not required for closeness (any triplet is fine), but if asked to return the first found or all tying triplets, add dedup skips.
Related problems
- 3Sum — exact zero
- 3Sum Smaller — count strictly less than target
- 4Sum — one more nested loop
- Two Sum