#16 3Sum Closest
the problem
In plain words
Pick three numbers from nums, at three different positions, whose sum is as close as possible to target. Return that sum. Exactly one closest sum exists.
in nums = [-1,2,1,-4], target = 1
out 2
-1 + 2 + 1 = 2 is at distance 1; no triple gets closer.
in nums = [0,0,0], target = 1
out 0
- 3 ≤ n ≤ 500
- -1000 ≤ nums[i] ≤ 1000
- -10⁴ ≤ target ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTwo pointers (opposite ends)
It's the 3Sum scan with a different goal: instead of collecting exact hits, remember the closest sum seen. The sign of sum − target still tells you which pointer to move.
solutions
From brute force to optimal
Try all triples and keep the sum with the smallest distance to target.
- Three nested loops over i < j < k.
- If |sum − target| beats the best distance so far, remember sum.
n(n−1)(n−2)/6 triples — about 2·10⁷ for n = 500.
One best value.
class Solution { public int threeSumClosest(int[] nums, int target) { int best = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.length; i++) for (int j = i + 1; j < nums.length; j++) for (int k = j + 1; k < nums.length; k++) { int sum = nums[i] + nums[j] + nums[k]; if (Math.abs(sum - target) < Math.abs(best - target)) best = sum; } return best; }}Sort, fix nums[i], converge left/right on the rest, and update the best on every sum.
- Sort; best = nums[0] + nums[1] + nums[2].
- For each i: left = i + 1, right = n − 1.
- If |sum − target| < |best − target|, best = sum.
- sum < target → left++; sum > target → right--; equal → return sum at once.
O(n log n) sort + n scans of O(n): about 125,000 steps for n = 500.
Ignoring the sort's O(log n) stack.
class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int best = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.length - 2; i++) { int left = i + 1, right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (Math.abs(sum - target) < Math.abs(best - target)) best = sum; // closer → remember it if (sum < target) left++; // need a bigger sum else if (sum > target) right--; // need a smaller sum else return sum; // distance 0: nothing can beat it } } return best; }}in the room
How to say it in the interview
talk track
- Say it's 3Sum with a different stopping rule: track the best sum instead of collecting matches.
- Justify the move: if sum < target, this left with any smaller right is even further below target, so left can go.
- Mention the early exit: a distance of 0 can't be beaten.
traps
- Starting best at
Integer.MAX_VALUE:best − targetthen overflows. Start from a real triple's sum. - Moving a pointer before updating best, so the closest sum is never recorded.
what they ask next
Follow-ups
3Sum Smaller (LC 259): count triples with sum < target?
Same sort + two pointers. When nums[i] + nums[left] + nums[right] < target, every right' in (left, right] also works, so add right − left and move left.
Should you skip duplicate anchors here too?
You may — if (i > 0 && nums[i] == nums[i − 1]) continue; saves time — but it isn't needed for correctness, because you return a sum, not a list of triplets.
before you submit
Edge cases to test
- Exactly three numbers: their sum is the answer.
- Target far outside every possible sum: the smallest (or largest) triple wins.
- An exact hit: return it immediately — nothing can be closer.
- All sums on one side of target, e.g. [1, 1, 40, 41, 100] with target 81 → 82.
practise next
Similar problems
- #153SumMediumin Two Pointers
- #167Two Sum II - Input Array Is SortedMediumin Two Pointers