3Sum Closest
Find the sum of three numbers closest to a target in O(n²): sort, fix one number, and move two pointers toward the target.
Problem Understanding
3Sum Closest: given nums and a target, find three numbers whose sum is closest to target, and return that sum. Exactly one answer is guaranteed.
Example: nums = [-1, 2, 1, -4], target = 1 returns 2 (-1 + 2 + 1).
The Intuition: 3Sum, Keeping the Nearest Miss
This is 3Sum with a different goal. Sort the array, fix one number nums[i], and search the rest with two pointers lo and hi:
- Compute
s = nums[i] + nums[lo] + nums[hi]and keep it if|s − target|beats the best so far. - If
s < target, the sum must grow: moveloright. - If
s > target, it must shrink: movehileft. - If
s == target, nothing is closer: return it.
Because the array is sorted, each move discards only pairs that are guaranteed to be no closer, so trying n starting points with a linear squeeze is enough: O(n²).
Interactive Walkthrough
The fixed number nums[i] is filled and the pair lo, hi is shaded. Watch each sum compared with the best so far, and the pointers move toward the target.
Dry Run Table
Input: sorted [-4, -1, 1, 2], target = 1, starting best -4
| i | lo | hi | Sum | Best | Move |
|---|---|---|---|---|---|
| -4 | -1 | 2 | -3 | -3 | lo++ |
| -4 | 1 | 2 | -1 | -1 | lo++ |
| -1 | 1 | 2 | 2 | 2 | hi-- |
The closest sum is 2.
The Solution Template
Sort, fix one number, squeeze the other two.
3Sum Closest Code
1var threeSumClosest = function(nums, target) {2 nums.sort((a, b) => a - b);3 let best = nums[0] + nums[1] + nums[2];4 for (let i = 0; i < nums.length - 2; i++) {5 let lo = i + 1, hi = nums.length - 1;6 while (lo < hi) {7 const s = nums[i] + nums[lo] + nums[hi];8 if (Math.abs(s - target) < Math.abs(best - target)) best = s;9 if (s < target) lo++;10 else if (s > target) hi--;11 else return s;12 }13 }14 return best;15};
Edge Cases & Common Mistakes
- Exactly three numbers: one triple; the loop checks it once.
- Starting best at 0 or infinity: start from a real sum, or the comparison can return a value no triple makes.
- Forgetting to sort: the pointer moves only make sense on a sorted array.
- Comparing sums instead of distances: the goal is the smallest
|s − target|, not the smallest s.
Summary
Sort, fix each nums[i], and squeeze lo and hi toward the target, keeping whichever sum is closest. Move lo up when the sum is too small, hi down when too big, and return immediately on an exact hit. O(n²) time, O(1) extra space.
More practice: DSA interview questions with answers · patterns cheat sheet