3Sum Closest

The target does not identify the winning triplet. It tells each pointer which direction is still worth exploring.

The 3Sum Closest solution is to sort the array, fix one value, scan the remaining suffix with two pointers, and preserve the closest sum found so far. The direct search is cubic; the sorted scan reduces it to quadratic time. The durable skill is not memorizing “sort plus two pointers.” It is deriving pointer movement from the current sum’s relationship to the target.

Read the Contract First

You receive an integer array nums and an integer target. Choose three values from distinct indices and return their sum—the sum itself, not the values or their positions. The problem guarantees a unique closest-sum result.

For example:

nums = [-1, 2, 1, -4]
target = 1
answer = 2

The triplet [-1, 2, 1] produces 2, which is one unit from the target.

Duplicate values are allowed when they occupy different indices. Three zeroes therefore form a valid triplet in:

nums = [0, 0, 0]

The contract is about indices, not a set of distinct values. That distinction determines the pointer boundaries and means we do not need triplet-deduplication logic.

Start With the Cubic Baseline

The straightforward solution enumerates every increasing index triple:

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            current_sum = nums[i] + nums[j] + nums[k]

Because i < j < k, every candidate uses distinct indices. For each sum, keep the candidate with the smallest distance from target:

distance = abs(current_sum - target)

if distance < abs(best_sum - target):
    best_sum = current_sum

This baseline costs O(n³) time and O(1) auxiliary space apart from loop variables. It is still valuable: the implementation is easy to trust and can act as a correctness oracle for testing the optimized version on small random inputs.

The bottleneck is the third loop. We want to remove one dimension of enumeration without losing the ability to compare every potentially useful candidate.

Sort, Fix One Value, and Scan the Rest

Sort the array in ascending order:

[-1, 2, 1, -4] -> [-4, -1, 1, 2]

Now fix nums[i] as the first value. The other two values must come from the suffix beginning at i + 1:

left = i + 1
right = n - 1

The current candidate is:

current_sum = nums[i] + nums[left] + nums[right]

Sorting gives the pair search a directional structure:

• Moving left rightward increases or preserves nums[left].
• Moving right leftward decreases or preserves nums[right].

For a fixed i, imagine a grid of candidate pairs. Rows are left indices, increasing as you move downward. Columns are right indices, increasing as you move to the right. Only the triangular cells with left < right are legal. Moving down tends to increase the sum; moving left tends to decrease it.

That grid is the leverage. We can walk its boundary instead of visiting every cell—but only if we can prove which row or column segment is already dominated.

Derive the Pointer Movement

Let the current error be:

error = current_sum - target

The sign of that error determines which pointer can move the sum toward the target. The proof is local: evaluate one cell, identify a whole dominated segment in the pair grid, then move to the boundary of the remaining candidates.

When the sum is too small

Suppose the evaluated cell is (left, right) and:

current_sum < target

Look across the current left row toward smaller right columns. For every r < right, sorting gives nums[r] <= nums[right], so:

nums[i] + nums[left] + nums[r] <= current_sum < target

Those cells are no closer to the target than the cell we just evaluated. The entire row segment to the left of (left, right) is dominated and can be discarded.

The next useful move is therefore to advance left:

left += 1

That moves to the next row, where nums[left] is larger and the sum can increase. The current right column remains available because a larger left value paired with that right endpoint may get closer to the target. Any cells to the right of the evaluated cell have already been excluded by the scan history or do not exist when right starts at the end of the array.

When the sum is too large

Now suppose the evaluated cell is (left, right) and:

current_sum > target

Look down the current right column toward larger left rows. For every l > left, sorting gives nums[l] >= nums[left], so:

nums[i] + nums[l] + nums[right] >= current_sum > target

Those cells are no closer to the target than the cell we just evaluated. The entire column segment below (left, right) is dominated and can be discarded.

The next useful move is therefore to decrease right:

right -= 1

That moves to the previous column, where nums[right] is smaller and the sum can decrease. The current left row remains available because a smaller right value paired with that left endpoint may get closer to the target. Any cells below the evaluated cell have just been proved useless.

The two cases are mirror images: a below-target cell discards its smaller-right row segment and moves down to a larger left; an above-target cell discards its larger-left column segment and moves left to a smaller right. The exact row or column proof matters more than the slogan “move toward the target.”

When the sum matches

If current_sum == target, the distance is zero. No result can improve on zero, so return immediately.

Frontier invariant: For a fixed i, left and right bound the still-relevant frontier of the sorted pair grid. Before each move, record the current cell. If its sum is below the target, the smaller-right segment in its row is dominated and left advances. If its sum is above the target, the larger-left segment in its column is dominated and right decreases. Every discarded segment is no closer than the evaluated cell.

The invariant explains both progress and safety: one pointer moves inward on every iteration, and the move removes only candidates whose sorted relationship to the current cell proves they cannot improve the objective.

Preserve the Best Sum Globally

The current sum is only one point in the search. A better result may have appeared under an earlier fixed value, so maintain best_sum across every outer iteration.

Initialize it from a valid triplet rather than from 0:

best_sum = nums[0] + nums[1] + nums[2]

Zero has no special status. The closest sum can be negative, positive, or on either side of the target.

At every visited state:

if abs(current_sum - target) < abs(best_sum - target):
    best_sum = current_sum

The strict comparison is appropriate because the problem guarantees a unique answer. A related problem could require a tie-break rule, but that rule must come from its contract rather than from habit.

Dry Run: Follow the State

Use:

nums = [-1, 2, 1, -4]
target = 1

After sorting:

nums = [-4, -1, 1, 2]

Initialize:

best_sum = -4 + -1 + 1 = -4

For i = 0, the fixed value is -4:

left = 1  -> -1
right = 3 -> 2
current_sum = -4 + -1 + 2 = -3

The sum is too small. In the current left row, smaller right columns can only make the sum smaller, so discard that dominated row segment and advance left:

left = 2  -> 1
right = 3 -> 2
current_sum = -4 + 1 + 2 = -1

This is still below the target. The pointers meet, so this outer iteration ends. The best sum is now -1, at distance 2 from the target.

For i = 1, the fixed value is -1:

left = 2  -> 1
right = 3 -> 2
current_sum = -1 + 1 + 2 = 2

Its distance is 1, so best_sum becomes 2. The sum is too large; larger left rows in the current right column would only increase the sum, so decrease right. The pointers meet and the scan ends.

Return 2.

The useful detail is that the best answer appears under the later outer index. The inner scan finds the best candidate for one fixed value, not necessarily the best triplet globally. That is why best_sum must survive every outer iteration.

With nums = [0, 0, 0] and target = 1, the only valid triplet produces 0. The loop records it, moves a pointer, and terminates when left and right meet.

Python Implementation

def three_sum_closest(nums: list[int], target: int) -> int:
    nums.sort()
    n = len(nums)

    best_sum = nums[0] + nums[1] + nums[2]

    for i in range(n - 2):
        left = i + 1
        right = n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            if abs(current_sum - target) < abs(best_sum - target):
                best_sum = current_sum

            if current_sum == target:
                return current_sum
            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return best_sum

Each variable has a specific obligation:

• i chooses the fixed first index.
• left and right choose two later, distinct indices.
• current_sum is the state currently being evaluated.
• best_sum stores the closest result found across all evaluated frontier states.

The control flow mirrors the derivation: calculate, preserve an improvement, stop on an exact match, then move according to the sign of the error.

This implementation mutates nums because nums.sort() sorts in place. If the caller's order must remain unchanged, sort a copy instead:

values = sorted(nums)

Skipping duplicate values for i is optional here. It can reduce repeated work when many values are equal, but it is not required for correctness because the goal is one sum, not a list of unique triplets. Add deduplication only when you can name the obligation it serves.

Correctness and Complexity

The outer loop uses range(n - 2), so it stops at the last index that leaves two values after i. The inner pointers begin at i + 1 and n - 1, and the loop runs only while left < right. Every evaluated state therefore satisfies:

i < left < right

and uses distinct indices.

For a fixed i, consider an evaluated pair (left, right).

• If its sum is below target, every pair (left, r) with r < right has a sum no larger than the current sum. Those cells are even farther below the target, so discarding that row segment and advancing left is safe.
• If its sum is above target, every pair (l, right) with l > left has a sum no smaller than the current sum. Those cells are even farther above the target, so discarding that column segment and decreasing right is safe.
• If its sum equals target, the distance is already zero and the search can stop.

Thus each move discards only the row or column segment proven no closer by fixed-coordinate monotonicity. The algorithm records the current frontier state before moving, and best_sum retains the closest recorded sum across every fixed i. When the loops finish, it is the closest valid triplet sum.

Sorting costs O(n log n). For each of the O(n) fixed values, either left or right moves toward the other, so the inner scan costs O(n). Therefore:

• Time: O(n log n + n²), which simplifies to O(n²).
• Auxiliary space: O(1) beyond the input array under the usual convention that excludes sorting workspace. Python's in-place sort may use additional implementation-managed memory.

Edge Cases and Common Failures

• Exactly three values: The initial triplet is the only candidate.
• All values equal: Equality and pointer termination must still work.
• Duplicate values: Repeated values are valid when their indices are distinct.
• Negative values or targets: Pointer direction comes from current_sum versus target, not from the signs of individual values.
• Target below every achievable sum: The answer may be the smallest achievable sum.
• Target above every achievable sum: The answer may be the largest achievable sum.
• Exact match: Return after evaluating it.
• Off-by-one errors: Use range(n - 2), set left = i + 1, and continue only while left < right.
• Moving both pointers by default: Move only the pointer whose direction can reduce the current error.
• Bad initialization: best_sum = 0 gives the answer an arbitrary bias and can fail when the closest result is negative.
• Input mutation: In-place sorting changes nums.
• Tie handling: The supplied contract guarantees a unique result; do not invent a tie rule.

The transferable move is narrower than “use two pointers”: when sorted coordinates make moving one pointer predictably increase the evaluated sum and moving the other predictably decrease it, fix one coordinate and walk the remaining pair grid's frontier. Reuse the pattern only when you can name the dominated row or column segment that each move removes. The proof earns the optimization; the visual metaphor does not.

Evaluate the state. Preserve the best result. Let the objective decide which pointer moves. That is the reasoning move worth carrying to the next problem.