Two Sum II - Input Array Is Sorted

Two Sum II looks like the classic Two Sum, but one detail changes everything: the array is already sorted. That single fact lets us drop the hash map and solve it with two pointers in O(1) extra space.

The slow way first

You could try every pair with two nested loops, just like brute-force Two Sum — that is O(n²). You could also reuse the hash-map trick for O(n) time, but it costs O(n) extra space and ignores the gift we were given: the array is sorted.

The question to ask: the array is sorted — what does that let me skip? Because the values increase from left to right, I always know which direction makes a sum bigger or smaller. That is enough to walk in from both ends.

The idea: squeeze from both ends

Put one pointer l at the smallest number (left end) and another pointer r at the largest (right end). Look at their sum:

• If sum > target, the largest number is too big — move r left to a smaller value.
• If sum < target, the smallest number is too small — move l right to a bigger value.
• If sum == target, we found the pair.

Every step throws away one number that can never be part of the answer, so the two pointers meet in a single pass.

Walk through it

Step through the animation. We start with l at 2 and r at 15: 2 + 15 = 17, too big, so r moves left. Now 2 + 11 = 13, still too big, r moves again. Then 2 + 7 = 9 — that hits the target, and we return the 1-based indices [1, 2].

Pseudocode

l = 0, r = last index
while l < r:
    sum = numbers[l] + numbers[r]
    if sum == target:
        return [l + 1, r + 1]     # 1-based indices
    if sum > target:
        r = r - 1                 # largest is too big, shrink from the right
    else:
        l = l + 1                 # smallest is too small, grow from the left
return []                         # (problem guarantees we never reach here)

The Python solution

def two_sum(numbers, target):
    l, r = 0, len(numbers) - 1
    while l < r:
        s = numbers[l] + numbers[r]
        if s == target:
            return [l + 1, r + 1]
        if s > target:
            r -= 1
        else:
            l += 1
    return []

• l and r start at the two ends of the array.
• s = numbers[l] + numbers[r] is the current sum of the two candidates.
• If s equals the target, we return [l + 1, r + 1] — this problem is 1-indexed, so we add one to each pointer.
• If s is too big, only r -= 1 can help: every value to the left of r is smaller.
• If s is too small, only l += 1 can help: every value to the right of l is larger.
• The loop ends when l meets r; the problem guarantees a pair exists before that.

Complexity

The two-pointer version matches the hash map on time but wins on space: it needs only two integer variables. That is the payoff for exploiting the sorted order.

When this pattern shows up

Practice