Coding · Two pointers
Closest Pair to a Target in a Sorted Array
- Reported once
- Medium
- campus SDE (2021)
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
You get an array of integers sorted in ascending order and a target number. Pick two different positions whose values add up as close to the target as possible and return those two values as [smaller, larger], breaking ties by the smaller sum, then the smaller first value, and returning [] when there are fewer than two elements. For [2,5,9,14,20] and target 17 the answer is [2,14], because 16 is only 1 away. The array can hold up to 100,000 values.
Restated in our own words, not a quote from Paytm or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: is the array really sorted in ascending order, and may it hold duplicates or negatives? Must the two values come from different positions, even when they are equal numbers? If two pairs are equally close, which one do I return? Do you want the values or the positions? What comes back when there are fewer than two elements? How large can the array be?
I would assume ascending order, duplicates and negatives allowed, two distinct positions, values returned as [smaller, larger], ties broken by the smaller sum and then the smaller first value, and [] for fewer than two elements. At 100,000 elements I want a single linear pass.
Brute force
Say the obvious answer and why it is too slow.
Check every pair of positions with two nested loops, compute the gap between the pair's sum and the target, and keep the best. That is O(n²) time and O(1) space. With n = 100,000 there are about five billion pairs, far too many for a normal time limit.
The loops ignore the one thing the input gives us for free: it is already sorted. A better first step is to fix one element and binary search for the partner that makes the sum nearest the target, which is O(n log n). That is respectable, but it still repeats a search from scratch for every element, while the sorted order lets both ends of the array make progress together in a single pass.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n)
- Space
- O(1) extra
The pattern is opposite-end two pointers on sorted data. Put left on the smallest value and right on the largest. Look at their sum. If it is below the target, move left up; if it is above, move right down; if it hits the target exactly, nothing can beat it, so stop. Along the way remember the pair with the smallest gap, using the smaller sum to break ties.
Why it is safe to discard a pointer: suppose the sum is below the target. Every other partner for left still in play lies between the two pointers, so it is no larger than the value at right, and its sum is no larger than the current sum, hence no closer to the target. Partners to the right of right were ruled out earlier. So the current pair beats or matches every remaining pair that uses left, and left can retire for good. The mirror argument retires right when the sum is too big. Each step retires one index, so the loop runs fewer than n times, and no pair that could be the best is ever skipped.
The difference from the exact-match two-sum version is that we compare gaps, not just equality, and we keep the best seen so far. Because left only moves right, the first pair found with a given sum has the smaller first value, which is why a strict "better than" check keeps the intended tie-break. I would say it aloud as: too small, so raise the low end; too big, so lower the high end.
Walk it through
A dry run on the example, step by step.
| Step | Pointers | Sum | Gap | Best pair | Move |
|---|---|---|---|---|---|
| 1 | L=0, R=4 | 22 | 5 | [2,20] | R down |
| 2 | L=0, R=3 | 16 | 1 | [2,14] | L up |
| 3 | L=1, R=3 | 19 | 2 | [2,14] | R down |
| 4 | L=1, R=2 | 14 | 3 | [2,14] | L up |
| 5 | L=2, R=2 | - | - | [2,14] | stop |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Use [2,5,9,14,20] with target 17. The trace table follows the pointers and the best pair so far.
Pointers at 2 and 20: the sum is 22, which is 5 too big, so best is [2,20] and right moves down. At 2 and 14 the sum is 16, only 1 below the target, so best becomes [2,14] and left moves up. At 5 and 14 the sum is 19, a gap of 2, not an improvement, and it is too big, so right moves down. At 5 and 9 the sum is 14, a gap of 3, still not better, and it is too small, so left moves up. Now both pointers sit on index 2, the loop stops, and the answer is [2,14].
The code
Runnable JavaScript, checked against test cases.
function closestPairToTarget(sorted, target) {
let left = 0;
let right = sorted.length - 1;
let bestPair = [];
let bestGap = Infinity;
let bestSum = Infinity;
while (left < right) {
const sum = sorted[left] + sorted[right];
const gap = Math.abs(sum - target);
if (gap < bestGap || (gap === bestGap && sum < bestSum)) {
bestGap = gap;
bestSum = sum;
bestPair = [sorted[left], sorted[right]];
}
if (sum < target) left++;
else if (sum > target) right--;
else break;
}
return bestPair;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Fewer than two elements: the condition left < right is false from the start, so the code returns the empty list. Exactly two elements: one iteration, and that pair is returned.
Duplicates such as [3,3,3] with target 6 work because pointers sit on different positions, so the pair [3,3] is valid. An exact hit stops the loop at once. If every possible sum is below the target, the pointer walk ends on the two largest values, which is correct. If every sum is above, it ends on the two smallest. Negative numbers need no special case, since only sums and gaps are compared. For a tie between sums on both sides of the target, such as 9 and 11 for target 10, the strict comparison with the sum check keeps the smaller sum 9.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the positions instead of the values, and what changes if the input is not sorted?
- How would you find three numbers whose sum is closest to the target, and what is the time?
- What if you need the k pairs closest to the target, and which structure would you add?
- If many different targets are queried against the same array, can you do better than one pass per query?
- How would you change the code if the two values had to come from two different sorted arrays?
Where candidates slip
The mistakes this problem punishes.
The classic slip is looping while left <= right, which lets an element pair with itself. Another is copying the exact-match two-sum habit and returning nothing when no pair hits the target; here the best near miss is the answer.
Some candidates track only the largest sum below the target and ignore pairs above it, but a pair 1 above can beat a pair 3 below. Others compare the signed difference rather than its absolute value. Moving both pointers in the same step skips pairs. Forgetting the tie-break rule, or updating on a tie so the later pair wins, returns a different pair than expected. Finally, sorting an already sorted array wastes time, and assuming it is unsorted leads to the quadratic loop.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.