/Interview Study Guide/Algorithms & data structures
#26

3Sum Closest

medium
Open in editor
arraytwo-pointerssorting

Given an integer array nums of length at least 3 and an integer target, pick exactly three distinct elements whose sum is as close to target as possible.

Return that closest sum. The input is guaranteed to have exactly one such closest sum.

Example

Input: nums = [-1,2,1,-4], target = 1
Output: 2

The closest sum is (-1) + 2 + 1 = 2, which is 1 away from the target.

Constraints

  • 3 <= nums.length <= 500
  • -1000 <= nums[i] <= 1000
  • -10^4 <= target <= 10^4
  • Exactly one closest sum exists.

Intuition

A first pass just adds up every possible triple of numbers and remembers whichever sum lands nearest the target, comparing distances with Math.abs.

function threeSumClosest(nums, target) {
  // Seed the answer with any triple's sum so the first comparison has something to beat.
  let best = nums[0] + nums[1] + nums[2];
  // Check every distinct triple of indexes.
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        const sum = nums[i] + nums[j] + nums[k];
        // Keep whichever sum sits closer to the target on the number line.
        if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
      }
    }
  }
  return best;
}
Brute force — every triple, track the closest: O(n³).

This is O(n³) — far more work than necessary. Can we do better?

It's the same shape as 3Sum: if we fix one number nums[i], the rest of the job is finding the pair in the suffix whose sum brings nums[i] + pair closest to target — which is exactly the Two pointers pair-sum problem.

That two-pointer trick only works on a sorted array, so sort the input first. For each fixed i, converge two pointers over the suffix: when the triple sum is below target move left up to grow it, when it's above move right down to shrink it. The difference from 3Sum is the goal — instead of waiting for an exact zero, we track the smallest |sum − target| seen, and return early only if we hit target exactly.

Walking it through:

sorted: [-4, -1, 1, 2] · target = 1

i↓
-40
L↓
-11
12
R↓
23
sum −3 · |−3−1| = 4 → best = −3, −3 < 1 so L++

Fix i = −4. First candidate −3 seeds the best distance.

i↓
-40
-11
L↓
12
R↓
23
sum −1 · |−1−1| = 2 → closer, best = −1, −1 < 1 so L++

Still short of target, so left keeps climbing — but −1 is nearer than −3.

-40
i↓
-11
L↓
12
R↓
23
sum 2 · |2−1| = 1 → closer, best = 2, 2 > 1 so R−−

Fix i = −1: [−1, 1, 2] sums to 2, distance 1 — overshoots, so right would retreat.

-40
i↓
-11
L↓R↓
12
23
L = R → suffix exhausted, no exact hit

Pointers meet; no triple ever equals target. Final answer: the closest sum, 2.

Optimization

Sort + two pointers

Sort the array. Fix the first element nums[i], then sweep the remaining range with two pointers lo/hi: each nums[i] + nums[lo] + nums[hi] is a candidate sum. If the sum is below target advance lo (need bigger), if above retreat hi (need smaller), and track the candidate with the smallest absolute distance to target throughout. An exact hit returns immediately.

O(n²) time (one pointer sweep per fixed i), O(1) extra space beyond the sort.

function threeSumClosest(nums, target) {
  // Sorting lets two pointers converge: a small sum means move right, a large sum means move left.
  nums.sort((a, b) => a - b);
  // Seed the answer with any valid triple so the first distance comparison has something to beat.
  let best = nums[0] + nums[1] + nums[2];
  // Fix the first element; the suffix after it is the pair we still have to choose.
  for (let i = 0; i < nums.length - 2; i++) {
    let lo = i + 1;            // smallest remaining value
    let hi = nums.length - 1;  // largest remaining value
    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];
      // Keep the sum nearest the target on the number line.
      if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
      // An exact match can never be beaten, so stop early.
      if (sum === target) return sum;
      // Too small: only a bigger value can help, so raise the low pointer; otherwise lower the high one.
      if (sum < target) lo++;
      else hi--;
    }
  }
  return best;
}

Complexity analysis

Time complexity: O(n²). Here's why:

  • Sorting the array takes O(n log n).
  • Then, for each of the n choices of the fixed element i, a two-pointer scan sweeps the suffix in O(n).

So the scans cost n × O(n) = O(n²), which dominates the sort — the overall time is O(n²).

Space complexity: O(1) auxiliary. Here's why:

  • The scan keeps only a handful of variables — best, lo, hi, and the running sum.
  • No extra arrays or maps are built; the answer is a single number, not a collection.

Sorting in place adds at most O(log n) for the sort's own stack, and the input array itself isn't counted as auxiliary space.

Test cases

Beyond the example above, these are worth thinking through before you submit.

InputExpected outputDescription
nums = [3,7,1], target = 1211Smallest input — the only triple, so its sum 3+7+1 is the answer.
nums = [4,4,4,4], target = 512All equal — every triple sums to 12; closest is forced.
nums = [-6,-3,0,2], target = -7-7Negative target hit exactly — −6+−3+2 = −7 returns early.
nums = [0,1,3,5], target = 54Tie: sums 4 and 6 are equidistant; strict `<` keeps the first-seen 4.
nums = [-1,-1,3,3], target = 21Duplicate values — closest sum −1+−1+3 = 1 sits one below target.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor