3Sum Closest
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Sort the array first, fix one element in an outer loop, then run converging two pointers on the remainder — track the closest sum found so far , moving left or right depending on whether the current sum is below or above target.
Constraints
- 3 ≤ nums.length ≤ 500
- -1000 ≤ numsi ≤ 1000
- -104 ≤ target ≤ 104
Example
nums = [-1, 2, 1, -4], target = 12Explanation The sum that is closest to the target is 2 (-1 + 2 + 1 = 2).
Fix one element, converge two pointers, track the closest sum
Sort the array. Anchor at index 0 (-4). sum = -4 + -1 + 2 = -3, closer than the initial -4 — closest = -3. Move left inward.
What happens in this step
i = 0 (value -4) left = 1 (value -1), right = 3 (value 2) sum = -4 + -1 + 2 = -3, |sum - target| = |-3 - 1| = 4 previous closest = -4, |closest - target| = 5 4 < 5, so closest updates to -3. sum (-3) < target (1), so left moves inward from index 1 to index 2.
Steps to visualize
- Sort the array so nearby values sit together.
- Fix the leftmost unfixed element as the anchor and set left just after it, right at the end.
- Track the closest sum found so far by comparing its distance from target.
- If the current sum is less than target, move left inward; if it is greater, move right inward.
- Stop the moment the sum exactly equals target, since no closer sum is possible.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Sort the array. Anchor at index 0 (-4). sum = -4 + -1 + 2 = -3, closer than the initial -4 — closest = -3. Move left inward.
What happens in this step
i = 0 (value -4) left = 1 (value -1), right = 3 (value 2) sum = -4 + -1 + 2 = -3, |sum - target| = |-3 - 1| = 4 previous closest = -4, |closest - target| = 5 4 < 5, so closest updates to -3. sum (-3) < target (1), so left moves inward from index 1 to index 2.
Solution
function threeSumClosest(nums, target) {
const sorted = [...nums].sort((a, b) => a - b);
let closest = sorted[0] + sorted[1] + sorted[2];
for (let i = 0; i < sorted.length - 2; i++) {
let left = i + 1;
let right = sorted.length - 1;
while (left < right) {
const sum = sorted[i] + sorted[left] + sorted[right];
if (Math.abs(sum - target) < Math.abs(closest - target)) {
closest = sum;
}
if (sum === target) {
return sum;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return closest;
}- Time
- O(n^2)
- Space
- O(n) (for the sort)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [-1, 2, 1, -4], target = 1 | 2 | example from the docstring |
nums = [1, 1, 1, 1], target = 3 | 3 | an exact match is found, so the distance is 0 |
nums = [-5, -4, -3, -2, -1], target = -100 | -12 | an all-negative array with a target far outside its range |
nums = [1, 1, 1], target = 100 | 3 | smallest valid input: only three elements |
nums = [1, 1, 1, 0], target = 100 | 3 | duplicate values among the candidates |
nums = [0, 2, 1, -3], target = -1 | -1 | a negative target that is hit exactly |