3Sum Closest

You are given an integer array nums and an integer target. Choose three elements at three different positions so that their sum is as close as possible to target, meaning the absolute difference between the sum and target is as small as possible.

Return that sum itself, not the difference. Each test is built so that exactly one sum value is closest; there is never a tie between a sum above target and one below it.

Example 1

Example 2

Example 3

Constraints

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104
• Exactly one sum value is closest to target.

Pattern Path · Two Pointers · problem 25 of 169

Start simple

Check all n·(n-1)·(n-2)/6 triples and keep the closest sum: O(n³) time, O(1) space.

The key idea

Sort the array. Then fix the smallest element of the triple, nums[i], and look for the best partner pair in the part to its right using two pointers lo = i + 1 and hi = n - 1.

At each step compute s = nums[i] + nums[lo] + nums[hi] and update the best answer if s is closer. Then move a pointer, and here sorting does the work:

• If s < target, every pair using the current lo with a smaller hi is even smaller, so none of them can beat s. Discard lo by moving it right.
• If s > target, the mirror argument discards hi.
• If s == target, the distance is 0 and nothing can do better, so return it.

Each move rules out a whole row or column of pairs that cannot improve the answer, so the pair search for one i is linear rather than quadratic. Over all i that is O(n²), which dominates the O(n log n) sort.

Complexity

• Time: O(n²)
• Space: O(1) extra (ignoring the sort)

Python

class Solution:
    def threeSumClosest(self, nums, target):
        nums = sorted(nums)
        best = nums[0] + nums[1] + nums[2]

        for i in range(len(nums) - 2):
            lo, hi = i + 1, len(nums) - 1
            while lo < hi:
                total = nums[i] + nums[lo] + nums[hi]
                if abs(total - target) < abs(best - target):
                    best = total
                if total < target:
                    lo += 1          # need a bigger sum
                elif total > target:
                    hi -= 1          # need a smaller sum
                else:
                    return total     # cannot get closer than exact
        return best

JavaScript

var threeSumClosest = function(nums, target) {
  nums = [...nums].sort((a, b) => a - b);
  let best = nums[0] + nums[1] + nums[2];

  for (let i = 0; i < nums.length - 2; i++) {
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const total = nums[i] + nums[lo] + nums[hi];
      if (Math.abs(total - target) < Math.abs(best - target)) best = total;
      if (total < target) lo++;         // need a bigger sum
      else if (total > target) hi--;    // need a smaller sum
      else return total;                // cannot get closer than exact
    }
  }
  return best;
};

What the interviewer is checking

It checks whether you can adapt the sorted two-pointer technique from an exact-match search to an optimisation, and justify why moving a pointer never skips the optimum.

Mistakes to avoid

• Returning the difference instead of the sum.
• Initialising the best sum to 0 or to an arbitrary large constant instead of the first real triple sum (or infinity on the distance).
• Forgetting to sort, which breaks the pointer-moving argument.
• Not stopping early when the sum equals the target, which is merely slower but easy to mention.

Follow-ups to expect

• What if you need four numbers? (Add an outer loop: O(n³).)
• Can duplicates be skipped for speed? (Yes, skip equal nums[i].)
• How do you count triples with sum below target? (Two pointers, add hi - lo.)

In real software

Picking a combination of items whose total lands nearest a budget or a nutritional goal, such as three products closest to a gift-card value, follows the same sort-then-squeeze search.

Practice next