Why the two-pointer solution to Two Sum II works

$ cat the-problem.mdThe problem

We are given an array numbers, sorted in non-decreasingNon-decreasing Each number is greater than or equal to the one before it. The order never goes down, but equal numbers may sit next to each other, as in 1, 2, 2, 5. order, and a target. Exactly one pair of numbers in the array adds up to target. We have to return the positions of those two numbers, counting from 1, and we may use only constant extra spaceConstant extra space The amount of extra memory the solution uses stays the same however large the input is: a few variables, never a copy of the input. Written O(1)..

Example 1

• Input: numbers = [1, 2, 4, 8, 9, 12, 15], target = 11
• Output: [2, 5]
• Why: $2 + 9 = 11$, and 2 and 9 are the 2nd and 5th numbers in the array.

Example 2

• Input: numbers = [3, 5, 5, 10], target = 10
• Output: [2, 3]
• Why: $5 + 5 = 10$. The two 5s are different elements, at positions 2 and 3, so using both is allowed.

Example 3

• Input: numbers = [-4, -1, 0, 6], target = -5
• Output: [1, 2]
• Why: $-4 + (-1) = -5$. The numbers can be negative.

$ cat introduction.mdIntroduction

There is a well-known solution to this problem that runs in $O(n)$ timeLinear time The number of steps grows in proportion to the length of the array. An array twice as long takes about twice as many steps. Written O(n). and uses $O(1)$ spaceConstant extra space The amount of extra memory the solution uses stays the same however large the input is: a few variables, never a copy of the input. Written O(1).. It uses two pointers, left and right. The solution itself is widely known, but not everyone understands why it works. This write-up explains the mathematics behind the solution, to make it clearer why the solution is correct.

$ cat the-math-behind-the-solution.mdThe math behind the solution

The two-pointer solution works because the array is sorted.

Suppose we have a sorted array $A$ with two pointers, left and right. Since the array is sorted, for every index $i$ between left and right we know:

$ cat the-three-cases.mdThe three cases

Now consider three cases.

1. The sum equals the target

We have found our pair.

2. The sum is greater than the target

Since $A[i] \ge A[\texttt{left}]$ for every $i$ between left and right, we can add $A[\texttt{right}]$ to both sides:

Therefore, every remaining pair that contains $A[\texttt{right}]$ has a sum greater than the target. We can eliminate all of these pairs at once by decrementing right.

3. The sum is less than the target

Similarly, since $A[i] \le A[\texttt{right}]$, we can add $A[\texttt{left}]$ to both sides:

Therefore, every remaining pair that contains $A[\texttt{left}]$ has a sum smaller than the target. We can eliminate all of these pairs at once by incrementing left.

The important insight is that each pointer movement eliminates an entire group of candidate pairsCandidate pair A pair of numbers that could still be the answer because nothing has ruled it out yet., not just the pair we examined. Because the array is sorted, we can prove that none of the eliminated pairs could be a solution, so we never need to examine them.

This is why we can reduce the search from $O(n^2)$Quadratic time The number of steps grows with the square of the length of the array. Checking every pair is quadratic: an array twice as long has about four times as many pairs. Written O(n²). to $O(n)$Linear time The number of steps grows in proportion to the length of the array. An array twice as long takes about twice as many steps. Written O(n)..

$ cat try-it-yourself.mdTry it yourself

The demonstration starts with the numbers from Example 1. Press Step to move a pointer. The first row is the array. The grid under it holds every pair of numbers in the array, so you can watch a whole row or column of pairs being ruled out by a single step. Change the target, or ask for new numbers, and step through again.

$ cat converting-the-math-into-code.mdConverting the math into code

Once you have the rules for the three cases, the idea is not difficult to implement. The solution needs three things:

1. Two pointers, left and right. The left pointer starts at the first element of the array and the right pointer starts at the last. These two pointers control when the loop ends.
2. A loop condition. The pair must be made of two different elements, so the loop runs while left < right and ends when the pointers meet.
3. An if statement inside the loop with three branches, one for each of the three cases.

$ cat complexity.mdComplexity

• Time complexity: $O(n)$. Every pass through the loop moves one of the pointers one step closer to the other, so the loop runs at most $n - 1$ times.
• Space complexity: $O(1)$.

$ cat code.mdCode

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        left = 0
        right = len(numbers) - 1
        answer = None
        while left < right:  # we need at least two numbers
            current_sum = numbers[left] + numbers[right]
            if current_sum == target:
                answer = [left + 1, right + 1]  # the answer counts from 1
                break
            elif current_sum > target:
                right -= 1
            else:
                left += 1

        return answer