You are given a list of numbers called numbers, sorted from smallest to largest, and a number target. Find the two numbers that add up to target. Return their positions, counting from 1, not from 0.
The list has up to 30,000 numbers, and they can be negative. Exactly one answer exists. You must use only O(1) extra memory, meaning a fixed handful of variables, no matter how long the list is.
This is 4.4.3 Two Sum with two changes. The list is sorted, which is a gift. And the memory limit rules out the hash map that solved Two Sum, since a map grows with the list.
So the question is: how can the sorted order replace the hash map?
Put one pointer on the smallest number, at the left end, and one on the largest, at the right end. Add the two numbers.
The sum is too small. We need a bigger sum. The only way to get one is to move the left pointer one step right, onto a larger number.
The sum is too big. We need a smaller sum. Move the right pointer one step left, onto a smaller number.
The sum is exactly right. Done.
Think of a see-saw with a row of children lined up by weight. You put the lightest child on one end and the heaviest on the other. If the heavy side wins, you swap in the next lighter child on that side. If the light side is up in the air, you swap in the next heavier child on the light side. Because the children are lined up by weight, the see-saw always tells you which side to change.
We go slowly here, because every two-pointer solution in this chapter rests on this one argument.
Suppose numbers[l] + numbers[r] is less than the target. Ask: "what could numbers[l] still pair with?" Its biggest possible partner is numbers[r], because the list is sorted and r is the far end of what is left. Even with that biggest partner, the sum is too small. So numbers[l] cannot reach the target with any remaining number. It can never be part of the answer. We can throw it away for good by moving l right.
The same argument works the other way. If the sum is too big, the smallest possible partner for numbers[r] is numbers[l]. Even that is too big. So numbers[r] can never be part of the answer, and we throw it away by moving r left.
So every move throws away one number that has been proved useless. No move ever needs to be undone.
This argument, "this number cannot be part of any answer, so dropping it is safe", is the proof behind every two-pointer solution. If you cannot make that argument for a problem, two pointers is the wrong tool for it.
(1) Start at the two ends.l points at the smallest number and r at the largest. Starting anywhere else would break the argument above, because we would not know that numbers[r] is the biggest partner left for numbers[l].
(2) Loop while l < r. We need two different positions. If l and r met, we would be adding a number to itself.
(3) Add the two numbers.
(4) Found it. Return both positions with 1 added to each, because the problem counts from 1. This + 1 is the most common slip on this problem.
(5) Too small, so drop the left number. Even the biggest partner was not enough, so numbers[l] is useless. Move l right.
(6) Too big, so drop the right number. Even the smallest partner was too much, so numbers[r] is useless. Move r left.
(7) A fallback. The problem promises an answer, so this never runs. It is there so the function always returns a list.
At step 1, 15 is dropped. Is that safe? The smallest partner 15 could have is 2, and 2 + 15 = 17 is already too big. So 15 can never be in the answer. The same reasoning drops 11 at step 2.
Time. Each turn of the loop moves exactly one pointer by one step: l goes right or r goes left. The pointers start n - 1 positions apart, and the loop stops when they meet. So there are at most n - 1 turns. Each turn does one addition and one or two comparisons, which is constant work. So the time is O(n).
Space. We keep three numbers: l, r and total. That does not grow with the list. So the extra memory is O(1), which meets the rule.
You could also solve this with binary search: for each number, search the sorted list for its partner, which takes O(\log n) per search. That is O(n \log n) in total. Two pointers is faster, because each step reuses what the last comparison taught us instead of starting a fresh search.
Negative numbers, such as [-5, -2, 3] with target −2. The pointer rules still work, because the list is sorted. Moving right always gives a bigger number, even among negatives. Here -5 + 3 = -2 on the first step.
Equal values, such as [3, 3, 4] with target 6. Step 1: 3 + 4 = 7, too big, drop the 4. Step 2: 3 + 3 = 6, found, return [1, 2].
The answer is the two ends. Found on the first step.
If the input is sorted, use two pointers. It needs no extra memory.
If the input is unsorted and you must return the original positions, use a hash map, as in Two Sum. Sorting would move the numbers and lose their positions.
If the input is unsorted but you only need the values, and memory is tight, you can sort first and then use two pointers.
"Why not use a hash map, like Two Sum?" They want the memory reason. A map uses O(n) extra memory. The sorted order lets two pointers do it in O(1).
"Prove that moving the left pointer is safe." They are checking the argument, not the code. The biggest partner left for numbers[l] is numbers[r], and even that was too small, so numbers[l] can never be part of the answer.
"What if there were many answers, and you had to return all of them?" Do not return on a match. Record the pair, move both pointers inward, and skip over equal neighbours so the same pair of values is not recorded twice.
"What if the list were sorted from largest to smallest?" Swap the two moves, or start l at the right end and r at the left. The logic is the same, mirrored.
One thing to volunteer: state the "this number can never be part of the answer" argument before you code. It is the proof that makes every two-pointer solution correct.
Next:4.5.3 3Sum. This loop wrapped inside another loop, where the real difficulty turns out to be skipping duplicates.