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
| Step | i / j / k | Sum / distance | Best sum / distance | Decision |
|---|---|---|---|---|
| 1 | — / — / — | — / — | -4 / 5 | nums.sort()Sort by value. Pointer indices refer to the sorted array; the original order stays visible above. |
| 2 | — / — / — | — / — | -4 / 5 | closest = sum(nums[:3])Start with a real triplet sum: -4 + -1 + 1 = -4, which is 5 away from the target 1. |
| 3 | 0 / 1 / 3 | -3 / 4 | -4 / 5 | j = i + 1; k = len(nums) - 1Fix nums[0] = -4. Search the values to its right with j and k. |
| 4 | 0 / 1 / 3 | -3 / 4 | -3 / 4 | if abs(total - target) < abs(closest - target): closest = totalDistance |-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. |
| 5 | 0 / 2 / 3 | -1 / 2 | -3 / 4 | j += 1j moves to index 2. Pairs with the old j and a smaller k sum no higher, so none can be closer. |
| 6 | 0 / 2 / 3 | -1 / 2 | -1 / 2 | if abs(total - target) < abs(closest - target): closest = totalDistance |-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. |
| 7 | 0 / — / — | — / — | -1 / 2 | j += 1j moves right and meets k. No pairs remain for this fixed value. |
| 8 | 0 / — / — | — / — | -1 / 2 | j < k → FalseThe search for fixed value -4 is complete. |
| 9 | 1 / 2 / 3 | 2 / 1 | -1 / 2 | j = i + 1; k = len(nums) - 1Fix nums[1] = -1. Search the values to its right with j and k. |
| 10 | 1 / 2 / 3 | 2 / 1 | 2 / 1 | if abs(total - target) < abs(closest - target): closest = totalDistance |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. |
| 11 | 1 / — / — | — / — | 2 / 1 | k -= 1k moves left and meets j. No pairs remain for this fixed value. |
| 12 | 1 / — / — | — / — | 2 / 1 | j < k → FalseThe search for fixed value -1 is complete. |
| 13 | — / — / — | — / — | 2 / 1 | return closestEvery 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 closestFor 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
Revisit 3Sum for the exact-match version, or Two Sum II for the original sorted pair search.