3Sum Closest

mediumWeak areas: redo your mistakes notebook + new32 stepsJava · Python · C++

Find three numbers whose sum is closest to the target. Sort, fix the first number, and move two pointers inward: a sum below the target moves the left pointer up, above it moves the right pointer down. Track the closest sum seen.

▶ Watch the animated trace

Traced input: nums = [-1, 2, 1, -4], target = 1 → 2. Original problem: leetcode.com/problems/3sum-closest/

Complexity

BestO(n²)

AverageO(n²)

WorstO(n²)

SpaceO(1)

Sorting plus an O(n) scan per first number.

Key idea

Same skeleton as 3Sum, but you keep the best distance instead of exact matches.
An exact match can return immediately.
Moving the pointer toward the target is the only move that can improve the distance.

Common mistakes

Initialising closest to a huge number and then overflowing on closest - target; start with the first triple.
Comparing sums instead of distances.

Solution

Java

int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int closest = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length - 2; i++) {
        int l = i + 1, r = nums.length - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (Math.abs(sum - target) < Math.abs(closest - target)) closest = sum;
            if (sum == target) return sum;
            if (sum < target) l++;
            else r--;
        }
    }
    return closest;
}

Python

def threeSumClosest(nums: List[int], target: int) -> int:
    nums.sort()
    closest = nums[0] + nums[1] + nums[2]
    for i in range(len(nums) - 2):
        l, r = i + 1, len(nums) - 1
        while l < r:
            total = nums[i] + nums[l] + nums[r]
            if abs(total - target) < abs(closest - target): closest = total
            if total == target: return total
            if total < target: l += 1
            else: r -= 1
    return closest

C++

int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int closest = nums[0] + nums[1] + nums[2];
    for (int i = 0; i + 2 < (int)nums.size(); i++) {
        int l = i + 1, r = (int)nums.size() - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (abs(sum - target) < abs(closest - target)) closest = sum;
            if (sum == target) return sum;
            if (sum < target) l++;
            else r--;
        }
    }
    return closest;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Exact match Returned immediately.	`nums = [0, 0, 0], target = 0`	`0`
Target far away The largest triple.	`nums = [1, 1, 1, 0], target = 100`	`3`
Negative target An exact triple exists: -5 + 0 + 3.	`nums = [4, 0, 5, -5, 3, 3, 0, -4, -5], target = -2`	`-2`