3Sum Closest (LeetCode 16)

The problem

You get an integer array nums (at least three numbers) and a target. Choose three numbers at different positions whose sum is as close as possible to target, and return that sum. There is exactly one best answer.

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

-1 + 2 + 1 = 2 is only 1 away from the target, and no other triplet gets closer.

How to think about it

Start with brute force. Check every triplet with three loops and keep the sum with the smallest |sum − target|. That’s O(n³).

The key insight: same skeleton as 3Sum. Sort the array and fix the first number nums[i]. For the other two, use converging pointers l and r. At each step you get a candidate sum s. Update the best answer if s is closer than anything so far. Then decide which way to move.

Why moving the pointers is safe. If s < target, the sum needs to grow, and the only move that can grow it is l += 1. Any pair using the current l with a smaller r would be even further below the target, so you lose nothing by dropping l. If s > target, the mirror argument applies to r. If s == target, the gap is zero and nothing can beat it, so return straight away.

Which pattern is this? Sort plus converging two pointers, the “optimise instead of match” variant. The tell is “closest to a target” on a sum over a small fixed number of elements.

Approach

1. Sort nums. Start best as the sum of the first three numbers.
2. For each i, set l = i + 1 and r = n - 1.
3. While l < r, compute s. If it’s closer to target than best, update best.
4. If s < target, move l right; if s > target, move r left; if equal, return s.
5. After all i, return best.

Solution

def three_sum_closest(nums, target):
    nums.sort(); best = nums[0] + nums[1] + nums[2]          # any valid start
    for i in range(len(nums) - 2):
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if abs(s - target) < abs(best - target): best = s  # closer: keep it
            if s < target: l += 1
            elif s > target: r -= 1
            else: return s                                     # exact hit
    return best
# three_sum_closest([-1,2,1,-4], 1) -> 2

Dry run

After sorting: [-4, -1, 1, 2], so best starts at -4 + -1 + 1 = -4.

No more pairs, so the answer is 2.

Complexity

• Time: O(n²). O(n log n) to sort, then an O(n) scan for each of the n choices of i.
• Space: O(1) extra (ignoring the sort’s internal memory).

Edge cases and pitfalls

• Exactly three numbers: best is already the only sum, and the loop confirms it.
• Initialising best to infinity works too, but then abs(best - target) needs care; starting from a real triplet avoids that.
• Large negatives: the gap is abs(s - target), not s - target. Forgetting the abs picks sums that are far below the target.
• Duplicates don’t need skipping here. They waste a little time but can’t produce a wrong answer, since you return a single number.
• Not returning early on an exact match is still correct, just slower.

Related problems

• 3Sum (LeetCode 15): the exact-match version, where duplicate skipping matters.
• Two Sum II – Input Array Is Sorted (LeetCode 167): the inner two-pointer step by itself.
• 4Sum (LeetCode 18): one more fixed loop on the same template.