3Sum Closest — Finding the Nearest Sum With Two Pointers

LeetCode 16: keep the 3Sum pointer structure, but judge every sum by its distance from the target.

How does the two-pointer strategy change when we want the closest sum instead of an exact match?

3Sum returns every unique triplet that sums to zero. 3Sum Closest returns a single number: the triplet sum with the smallest absolute distance from a given target. There is no list to build and no duplicates to filter, only a best answer to keep improving.

Step through the default input. The best sum changes only when a triplet lands nearer the target.

Chase the smallest distance

distance = |sum − target|

Original: [-1, 2, 1, -4]. Sorted: [-4, -1, 1, 2]. Target: 1.

Closest sum: 2.

Interactive playback requires JavaScript. The complete trace remains readable below.

Read all 13 steps
Stepi / j / kSum / distanceBest sum / distanceDecision
1— / — / —— / —-4 / 5nums.sort()

Sort by value. Pointer indices refer to the sorted array; the original order stays visible above.

2— / — / —— / —-4 / 5closest = sum(nums[:3])

Start with a real triplet sum: -4 + -1 + 1 = -4, which is 5 away from the target 1.

30 / 1 / 3-3 / 4-4 / 5j = i + 1; k = len(nums) - 1

Fix nums[0] = -4. Search the values to its right with j and k.

40 / 1 / 3-3 / 4-3 / 4if abs(total - target) < abs(closest - target): closest = total

Distance |-3 − 1| = 4 beats 5, so the best sum becomes -3. The sum is below the target, so move j right for a larger sum.

50 / 2 / 3-1 / 2-3 / 4j += 1

j moves to index 2. Pairs with the old j and a smaller k sum no higher, so none can be closer.

60 / 2 / 3-1 / 2-1 / 2if abs(total - target) < abs(closest - target): closest = total

Distance |-1 − 1| = 2 beats 4, so the best sum becomes -1. The sum is below the target, so move j right for a larger sum.

70 / — / —— / —-1 / 2j += 1

j moves right and meets k. No pairs remain for this fixed value.

80 / — / —— / —-1 / 2j < k → False

The search for fixed value -4 is complete.

91 / 2 / 32 / 1-1 / 2j = i + 1; k = len(nums) - 1

Fix nums[1] = -1. Search the values to its right with j and k.

101 / 2 / 32 / 12 / 1if abs(total - target) < abs(closest - target): closest = total

Distance |2 − 1| = 1 beats 2, so the best sum becomes 2. The sum is above the target, so move k left for a smaller sum.

111 / — / —— / —2 / 1k -= 1

k moves left and meets j. No pairs remain for this fixed value.

121 / — / —— / —2 / 1j < k → False

The search for fixed value -1 is complete.

13— / — / —— / —2 / 1return closest

Every fixed value has been searched. Return 2, at distance 1 from 1.

Closer means a smaller distance

distance = abs(current_sum - target)

A numerically smaller sum is not necessarily closer. With target 1, a sum of −3 is smaller than 2, yet it is four units away, while 2 is only one unit away. Every comparison must use distances, never the raw sums.

Target 1: sum -3 has distance 4; sum 2 has distance 1. 2 is closer.

Why the pointer moves still work

After sorting, i fixes one value, j starts just after it and k starts at the end. If the sum is below the target, every pair using the current j with a smaller k sums no higher, so none can be closer: move j right. If the sum is above the target, move k left for the mirror reason. If it equals the target, the distance is zero and nothing can beat it, so return immediately.

My accepted Python solution

closest starts as the sum of the first three sorted values, so it is always a real triplet sum. It changes only when a new distance is strictly smaller.

class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        nums.sort()
        closest = sum(nums[:3])

        for i in range(len(nums) - 2):
            j = i + 1
            k = len(nums) - 1

            while j < k:
                total = nums[i] + nums[j] + nums[k]

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

                if total < target:
                    j += 1
                elif total > target:
                    k -= 1
                else:
                    return total

        return closest

For each fixed i, j and k together cross the remaining range at most once, so the pointer search takes O(n²) time. It keeps only a few variables: O(1) auxiliary space, excluding the sort, which adds O(n log n) time and its own workspace.

What I got wrong first

I independently adapted the sorting, fixed-pointer and two-pointer structure from 3Sum. My first version compared sums numerically instead of comparing their absolute distance from the target. I also carried over duplicate-skipping logic that this problem does not need, and ran into indexing errors. I needed debugging assistance to complete the accepted approach above.

The lesson: reuse a pattern’s structure, but re-derive its comparison. 3Sum asks whether a sum is zero; 3Sum Closest asks whether it is nearer.

Problem details
Platform
LeetCode
Problem number
16
Problem difficulty
Medium
Pattern
Two Pointers — Fix One, Search Two
Solution language
Python 3

Official problem

Revisit 3Sum for the exact-match version, or Two Sum II for the original sorted pair search.