3Sum Closest: Tracking the Best Miss With Two Pointers

This one is a Medium-rated classic reported from Bloomberg, Amazon, Apple interviews: "3Sum Closest". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Two Pointers pattern on sight. Part 8 of 12 in the Two Pointers arc.

The Problem

Given an integer array nums and an integer target, find three integers whose sum is closest to target and return that sum. Exactly one answer is guaranteed. Unlike 3Sum, there is no early exit on a match's duplicates — you are minimizing a distance.

Input:  nums = [-1, 2, 1, -4], target = 1
Output: 2
The closest sum is -1 + 2 + 1 = 2.

Recognizing the Two Pointers Pattern

Two pointers means walking a sequence with two indices that move based on a comparison — from both ends inward, or slow-and-fast in one direction. It turns brute-force pair scans that cost O(n²) into a single O(n) pass, and it is usually the intended answer whenever the input is sorted or can be sorted cheaply.

Same skeleton as 3Sum — sort, anchor, converge — but the state you carry changes: instead of collecting exact hits you track the best-so-far distance. Recognizing that one pattern supports both exact-match and optimization queries is the point of this entry.

The Approach

Sort, fix each anchor, and run two pointers on the remainder. At every step compare abs(current - target) against the best gap seen and update. Then move the pointers exactly as in sorted Two Sum: sum too small advances left, too large retreats right.

An exact hit allows an immediate return — a small optimization that also shows you understand the distance can never beat zero.

Python Solution

def three_sum_closest(nums: list[int], target: int) -> int:
    """Sum of the triplet closest to target."""
    nums.sort()
    n = len(nums)
    best = nums[0] + nums[1] + nums[2]
    for i in range(n - 2):
        left, right = i + 1, n - 1
        while left < right:
            current = nums[i] + nums[left] + nums[right]
            if current == target:
                return current
            if abs(current - target) < abs(best - target):
                best = current
            if current < target:
                left += 1
            else:
                right -= 1
    return best

Complexity

• Time: O(n²) — anchor loop times linear convergence, sort dominated
• Space: O(1) — a single best-sum variable beyond the in-place sort

Interview Tips and Follow-Ups

• Initialize best from real elements, never infinity — returning a sentinel on tiny inputs is an instant bug report.
• Duplicate-skipping from 3Sum is an optional speedup here, not a correctness need — knowing the difference matters.
• Escalation: closest pair (2Sum closest) in a sorted array, same reasoning one level down.

More Two Pointers problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.