3Sum Closest: Two Pointers with Distance Tracking

LeetCode 3Sum Closest (problem 16, medium) is a natural follow-up to 3Sum. Instead of finding triplets that sum to exactly zero, you need to find the triplet whose sum is closest to a given target. The structure is almost identical, but the decision logic changes in an interesting way.

The problem

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input has exactly one solution.

Example: nums = [-1, 2, 1, -4], target = 1. The answer is 2 because -1 + 2 + 1 = 2 and |2 - 1| = 1 is the smallest possible distance from target.

The approach

The strategy follows the same blueprint as 3Sum:

1. Sort the array. This enables the two-pointer technique.
2. Fix one element at index i using an outer loop.
3. Run two converging pointers (lo and hi) on the remaining subarray.
4. Track the closest sum by comparing abs(current_sum - target) against the best distance seen so far.

The key difference from 3Sum: you are not looking for an exact match. You compare every triplet sum against the target and keep whichever sum has the smallest absolute difference. If you find an exact match (sum == target), you can return immediately.

The pointer movement logic stays the same. If the current sum is less than the target, move lo right to increase the sum. If the current sum is greater than the target, move hi left to decrease the sum. Each move brings you closer to the target from one direction.

Visual walkthrough

Let's trace through nums = [-4, -1, 1, 2] (already sorted) with target = 1. The purple pointer is i (fixed), orange is lo, and green is hi.

Notice the progression: the algorithm tries every possible fixed element, and for each one the two pointers sweep through the remaining subarray. Each triplet sum gets compared to the current closest. By the end, the closest sum found is 2 with a distance of just 1 from the target.

The code

def three_sum_closest(nums, target):
    nums.sort()
    closest = nums[0] + nums[1] + nums[2]
    n = len(nums)

    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        lo, hi = i + 1, n - 1

        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]

            if abs(s - target) < abs(closest - target):
                closest = s

            if s == target:
                return s
            elif s < target:
                lo += 1
            else:
                hi -= 1

    return closest

A few things to note:

• closest is initialized to the sum of the first three elements. This avoids dealing with infinity or special initial values.
• The duplicate skip on i (if i > 0 and nums[i] == nums[i - 1]: continue) is an optimization. It is not required for correctness (unlike in 3Sum where it prevents duplicate triplets), but it avoids redundant work.
• The early return if s == target: return s is an optimization. If the sum exactly equals the target, no other sum can be closer, so you can stop immediately.
• The pointer movement is identical to 3Sum: if s is below the target, move lo right; if above, move hi left.

Complexity

Time: O(n^2). Sorting is O(n log n). The outer loop runs up to n times, and each inner two-pointer scan is O(n). Total: O(n log n) + O(n^2) = O(n^2).

Space: O(1) extra. Only a few variables are used beyond the input. Sorting is done in-place (O(log n) stack space for the sort itself, but no auxiliary data structures).

The building blocks

This problem combines two reusable building blocks:

Sorted two-pointer scan

Fix one element, then use two pointers converging from opposite ends of the remaining sorted subarray. The sorted order guarantees that moving lo right increases the sum and moving hi left decreases it. This is the same inner loop used in 3Sum, Two Sum II, and Container With Most Water.

Distance tracking

Instead of checking for an exact match, you maintain a running "best" and update it whenever abs(current - target) is smaller than abs(best - target). This pattern appears in many optimization problems: closest pair, nearest value in BST, and any scenario where you want the minimum distance to a target rather than an exact hit.

When you can recognize these two bricks independently, the full solution assembles itself. Fix one element, run the two-pointer scan, and swap the equality check for a distance comparison.

Edge cases

• Exact match exists. If a triplet sums to exactly target, the early return triggers and you get the answer in fewer iterations.
• All negative numbers. For example, nums = [-5, -3, -1], target = -10. The only possible sum is -9, which gets returned. Sorting and the two-pointer logic work identically regardless of sign.
• Array of size 3. The smallest valid input. The outer loop runs once, the inner loop checks the only possible triplet, and that sum is returned. No pointer movement needed.

From understanding to recall

The 3Sum Closest algorithm is a small variation on 3Sum. Sort, fix one element, run two pointers. The only change is replacing the "does sum equal zero" check with "is this sum closer to target than the best so far." But under interview pressure, it is easy to mix up the details. Should you initialize closest to infinity or to an actual sum? Do you need the inner duplicate skips?

The answer is to drill the building blocks separately. If you can write a sorted two-pointer scan from memory and you understand distance tracking as a standalone concept, the full solution follows. You are not memorizing a new algorithm. You are recombining two patterns you already know, with a one-line change to the comparison logic.

Related posts

• 3Sum: Sorting Plus Two Pointers - The parent problem that this variant builds on
• Two Sum - The foundational complement-lookup pattern

---

Visual Learner? See how sorting algorithms work with our Quick Sort Visualization — the first step before applying two pointers.