Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Two Sum on a Sorted Array

Find two numbers in a sorted array that add up to a target using two pointers, in O(n) time and O(1) space, with a proof of why it works.

mediumPattern: Two Pointers

Updated Quick read: 3 min read

Approaches at a glance

ApproachTimeSpace
Hash mapO(n)O(n)
Two pointersO(n)O(1)

The problem

You are given an array of integers sorted in ascending order and a target number. Exactly one pair of elements adds up to the target. Return the positions of that pair, counting from 1 rather than 0, and use only constant extra space.

numbers = [2, 7, 11, 15], target = 9   →  [1, 2]    (2 + 7)
numbers = [2, 3, 4],      target = 6   →  [1, 3]    (2 + 4)
numbers = [-1, 0],        target = -1  →  [1, 2]    (-1 + 0)

Approach 1: hash map

The hash map solution to Two Sum works on any array, sorted or not: O(n) time, O(n) space. But it ignores the fact that the input is sorted, and it breaks the constant-space requirement.

Approach 2: two pointers

Put one pointer on the smallest number and one on the largest, and look at their sum.

  • If the sum equals the target, that is the answer.
  • If the sum is too small, move the left pointer right to get a larger number.
  • If the sum is too large, move the right pointer left to get a smaller number.

JavaScript

function twoSumSorted(numbers, target) {
  let left = 0;
  let right = numbers.length - 1;
 
  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) return [left + 1, right + 1];
    if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
  return [];
}

Python

def two_sum_sorted(numbers, target):
    left = 0
    right = len(numbers) - 1
 
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

Walkthrough

numbers = [1, 3, 4, 6, 8, 11], target = 10:

left right Sum Action
0 (1) 5 (11) 12 Too large, move right
0 (1) 4 (8) 9 Too small, move left
1 (3) 4 (8) 11 Too large, move right
1 (3) 3 (6) 9 Too small, move left
2 (4) 3 (6) 10 Found: return [3, 4]

Time O(n): every step moves one pointer, and they meet after at most n steps. Space O(1).

Why no pair is missed

It can look as if moving a pointer skips pairs that were never checked. It does, but only pairs that cannot be the answer.

Suppose the sum is too small. numbers[right] is the largest number still in play, so numbers[left] plus anything else available is no larger than the current sum, and is too small as well. numbers[left] cannot be in the answer, so dropping it loses nothing. The same reasoning removes numbers[right] when the sum is too large.

The full argument is in the two pointers pattern.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(twoSumSorted([2, 7, 11, 15], 9)); // [1, 2]
console.log(twoSumSorted([2, 3, 4], 6)); // [1, 3]

Python

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

The comment after each line is the result you should see.

Common mistakes

  • Returning 0-based indexes. This problem asks for positions starting at 1, hence the + 1.
  • Using left <= right. When the pointers meet they point at one element, and one element is not a pair.
  • Applying this to an unsorted array. The rule for moving pointers is only valid when the array is sorted.

Original problem: LeetCode 167: Two Sum II - Input Array Is Sorted