Given a sorted array, find two numbers that add up to a target — how do you do it in O(n) without extra space?

How to think about it

The interviewer has already sorted the array for you, and that is the whole hint. What they want to hear is that you notice the sort and let it pay for itself — no hash map, no extra space, just two pointers walking toward each other. If you reach for a dict here, you have ignored the gift they handed you.

The pattern fires on a simple signal: sorted input plus “find a pair.” Put one pointer at the smallest value and one at the largest, and read the sum. If it overshoots the target, the only way down is to pull the right pointer left toward smaller numbers. If it falls short, push the left pointer right toward larger ones. Each move discards a value you have proven cannot be part of the answer, so neither pointer ever backtracks — they cross exactly once, and the whole scan is one pass.

A worked example

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left + 1, right + 1]  # 1-indexed, LeetCode style
        elif s < target:
            left += 1                     # need bigger -> move left up
        else:
            right -= 1                    # need smaller -> move right down
    return []  # no solution found

print(two_sum_sorted([2, 7, 11, 15], 9))
print(two_sum_sorted([1, 3, 4, 6, 8], 10))
print(two_sum_sorted([1, 2], 3))

# Trace the convergence
def two_sum_sorted_verbose(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        print(f"  left={left} ({nums[left]}), right={right} ({nums[right]}), sum={s}")
        if s == target:
            return [left + 1, right + 1]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

print("Trace for [2,7,11,15], target=9:")
two_sum_sorted_verbose([2, 7, 11, 15], 9)

[1, 2]
[3, 4]
[1, 2]
Trace for [2,7,11,15], target=9:
  left=0 (2), right=3 (15), sum=17
  left=0 (2), right=2 (11), sum=13
  left=0 (2), right=1 (7), sum=9

Watch the trace squeeze the window. The first sum is 17, too big, so 15 is ruled out and the right pointer drops to 11; still too big, drop to 7; now 2 + 7 == 9 and we return the 1-indexed pair [1, 2]. Three reads found the answer in a four-element array — and the left pointer never had to move, because the two pointers travel at most n steps combined. That shared budget is what makes it O(n) time with only two index variables of memory.