How Do You Pick a Duet Partner?
In the singing-practice app "Harmony", every member has a pitch score. When two members sing together, the closer the sum of their scores is to the target harmony value T, the better the duet blends.
But there may be no two members whose scores sum to exactly T. So the goal isn't "a pair that sums to T" — it's "the pair whose sum is closest to T."
Example: scores
[12, 18, 25, 33, 41, 50], target 60. The answer is 59 (18 + 41) — only 1 away, so it's the closest.
The Simplest Approach and Its Limit
The first idea that comes to mind is to check every pair of members. Compute each sum and remember the pair with the smallest |sum - T|.
The catch: with N members there are about N²/2 pairs. At N = 100,000 that's 5 billion checks — far too slow. O(n²) won't finish in time.
The Key Idea: Use Sorting as a Weapon (Two Pointers)
There's a crucial premise here: the scores are sorted in ascending order. Exploiting this lets us find the answer without examining every pair.
Start with two pointers at both ends.
- •
leftpoints at the smallest value (left end),rightat the largest (right end) - •Compare the sum of the two values with target T:
- sum < T → too small → need a larger value → move left one step right
- sum > T → too large → need a smaller value → move right one step left
- sum == T → gap is 0, can't get closer, so it's the answer
- •At each pair, compare |sum - T| with the best so far and update best whenever it's closer.
Repeat until left meets right, and you're done.
"Why Is Moving Just One Pointer Safe?"
At first you might worry: "If I move only one pointer, won't I miss some pairs?" But because the array is sorted, it's safe.
Consider when the sum is below T. Right now right is at the far end, so it's paired with the largest possible value. If the sum is still too small, then any pair made by shrinking right will only have an even smaller sum — it can never get closer to T. So those pairs are safe to discard, and the only way to raise the sum is left++.
When the sum is above T, the symmetric logic holds. That's why each pointer moves in one direction only, and the whole thing finishes in O(n).
Complexity at a Glance
| Approach | Time | Notes |
|---|---|---|
| All-pairs check | O(n²) | Simple but infeasible for large N |
| Two pointers | O(n) | Requires sorting; each pointer moves one way |
| (If not sorted) | O(n log n) | Sort first, then two pointers |
Common Mistakes
- •Forgetting to initialize best: Without seeding best with the first pair, there's no baseline to compare against.
- •Comparing the gap without absolute value: Always compare with |sum - T| so sums above and below are treated fairly.
- •Skipping the sort check: If the input isn't guaranteed sorted, sort it first.
- •Wrong loop condition: Loop only while
left < rightso you never pick the same person twice.
See It in Action on AlgoNote
How the two pointers close in from both ends — and the exact moment best gets updated — is something you really need to see to fully grasp. Step through how the pointers react when the sum is above versus below the target.
Closest Pair Sum to Target - Watch the Step-by-Step Solution →