Skip to content
16-Week DSA Roadmap
LeetCode #167MediumProblem 2 of 8

Two Sum II - Input Array Is Sorted

In a sorted list, find the two numbers that add up to a target, using only a fixed amount of extra memory.

  • Converging two pointers
  • Sorted input

Before this, know: Arrays and indexes, Two Sum (week 1)

The problem in plain English

This is Two Sum from week 1 with two changes:

  1. The list numbers is sorted: every number is at least as big as the one before it, like [1, 3, 4, 6, 8].
  2. You must use only a fixed amount of extra memory (no hash map that grows with the input).

Find the two numbers that add up to target and return their positions. One more twist: here positions are counted from 1, not from 0. (Programmers call this “1-indexed”.)

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

numbers
  1. 10
  2. 31
  3. 42
  4. 63
  5. 84
4 + 6 = 10. They sit at indexes 2 and 3, which are positions 3 and 4 when counting from 1, so the answer is [3, 4].

The rules:

  • There is exactly one answer.
  • You can’t use the same position twice.
  • The first position in the answer must be the smaller one.
  • Numbers can be negative, and can repeat.

Before you code: think it through

In week 1 we solved Two Sum with a hash map: a lookup table that answers “have I seen this number?” in one step. That works here too, but the map can grow to hold every number, and this problem asks us not to use that memory. The sorted order is the hint that there’s another way.

Here’s the key fact. Start with left on the smallest number and right on the biggest, and look at their sum:

  1. 10
  2. 31
  3. 42
  4. 63
  5. 84
1 + 8 = 9 is less than 10. Since 8 is the biggest number there is, 1 + (anything else) is even smaller. So 1 can never be in the answer: cross it off.

Pause and think

Now left is on 3 and right is still on 8. 3 + 8 = 11, which is more than 10. Which number can we cross off, and why?

Every comparison crosses off one number for good. That’s why we never need to go back.

Approach 1: Brute force

Try every pair: pick a first number i, add it to every number j after it, and stop when the sum is target. This ignores the sorting completely.

Brute force: try every pair

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

numbers
  1. 10
  2. 31
  3. 42
  4. 63
  5. 84
variables
target
10
numbers[i] + numbers[j]
—
checks so far
0
  • First number (i)
  • Second number (j)
  • Pair that works

Pick numbers[0] = 1 as the first number, then try every number after it.

Step 1 / 12

Which line is running?

function twoSum(numbers, target) {Running now:   for (let i = 0; i < numbers.length; i++) {    for (let j = i + 1; j < numbers.length; j++) {      if (numbers[i] + numbers[j] === target) {        return [i + 1, j + 1]; // the problem counts positions from 1      }    }  }  return [];}

Brute force

function twoSum(numbers, target) {  for (let i = 0; i < numbers.length; i++) {    for (let j = i + 1; j < numbers.length; j++) {      if (numbers[i] + numbers[j] === target) {        return [i + 1, j + 1]; // the problem counts positions from 1      }    }  }  return [];}
def two_sum(numbers, target):    for i in range(len(numbers)):        for j in range(i + 1, len(numbers)):            if numbers[i] + numbers[j] == target:                return [i + 1, j + 1]  # the problem counts positions from 1    return []

Why is it slow?

With 5 numbers there are 4 + 3 + 2 + 1 = 10 pairs to check. With 30,000 numbers (LeetCode’s limit) there are about 30,000 × 29,999 ÷ 2 ≈ 450 million. The work grows like n × n, written O(n²): double the list, four times the work.

The week-1 hash map fixes the time (one pass, O(n)) but needs a map that can hold every number: O(n) extra memory. With a sorted list we can have both: one pass and no map.

The pattern: converging two pointers

Pattern

Converging two pointers

Template

Use it when: the input is sorted (or you can sort it) and you're looking for a pair whose sum, difference or comparison hits a goal.

Signal words

  • “sorted array”
  • “two numbers that add up to”
  • “pair with sum”
  • “constant extra space”
  • “1-indexed”

Approach 2: Two pointers on the sorted list

  1. Put left on index 0 (the smallest number) and right on the last index (the biggest).
  2. Add them up: sum = numbers[left] + numbers[right].
  3. If sum equals target, return [left + 1, right + 1] (positions count from 1).
  4. If sum is too small, the left number is useless: move left one step right.
  5. If sum is too big, the right number is useless: move right one step left.
  6. Repeat while left is smaller than right.

Watch the faded boxes: each one is a number we’ve proved can’t be in the answer. The shaded stretch between the pointers is everything still “in play”, and it shrinks by one every step.

Two pointers on a sorted list

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

numbers (sorted)
  1. 10
  2. 31
  3. 42
  4. 63
  5. 84
variables
target
10
sum
—
sum vs target
—
answer (1-based)
—
  • left
  • right
  • Ruled out for good
  • The pair

The list is sorted, smallest to largest. Put left on the smallest number (1) and right on the largest (8). Their sum tells us which way to move.

Step 1 / 9

Which line is running?

function twoSum(numbers, target) {  let left = 0;Running now:   let right = numbers.length - 1;  while (left < right) {    const sum = numbers[left] + numbers[right];    if (sum === target) {      return [left + 1, right + 1]; // the problem counts positions from 1    } else if (sum < target) {      left++; // too small: we need a bigger number    } else {      right--; // too big: we need a smaller number    }  }  return [];}

Try the negatives example. Nothing changes: “too small, move left; too big, move right” works for any numbers, as long as the list is sorted.

The code, line by line

Two pointers on a sorted list

function twoSum(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]; // the problem counts positions from 1    } else if (sum < target) {      left++; // too small: we need a bigger number    } else {      right--; // too big: we need a smaller number    }  }  return [];}
def two_sum(numbers, target):    left, right = 0, len(numbers) - 1    while left < right:        total = numbers[left] + numbers[right]        if total == target:            return [left + 1, right + 1]  # the problem counts positions from 1        elif total < target:            left += 1  # too small: we need a bigger number        else:            right -= 1  # too big: we need a smaller number    return []

On LeetCode the function is var twoSum = function(numbers, target) in JavaScript, and def twoSum(self, numbers, target) inside class Solution in Python. The body is the same.

  • Line 1: define the function with the sorted list and the target.
  • Lines 2–3 (JS) / line 2 (Python): the two pointers, on the first and last index. Python sets both on one line: left, right = 0, len(numbers) - 1.
  • Line 4 (JS) / line 3 (Python): keep going while there are still two different numbers between the pointers.
  • Line 5 (JS) / line 4 (Python): add the two numbers. (In Python we call it total because sum is already the name of a built-in function.)
  • Lines 6–7 (JS) / lines 5–6 (Python): found it. Add 1 to each index, because this problem counts positions from 1.
  • Lines 8–9 (JS) / lines 7–8 (Python): too small. The left number can’t reach the target even with the biggest partner, so move left up to a bigger number.
  • Lines 10–11 (JS) / lines 9–10 (Python): too big. The right number overshoots even with the smallest partner, so move right down to a smaller number.
  • The last line: LeetCode promises an answer, so we never get here. It keeps the function returning a list either way.

Dry run

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

stepleftrightnumbers[left] + numbers[right]comparemove
1041 + 8 = 9< 10left → 1 (cross off 1)
2143 + 8 = 11> 10right → 3 (cross off 8)
3133 + 6 = 9< 10left → 2 (cross off 3)
4234 + 6 = 10= 10return [3, 4]
numbers = [1, 3, 4, 6, 8], target = 10

Look at steps 1 and 3: the sum was 9 both times, but the pointers were in different places, and each time a different number got crossed off. Four comparisons instead of up to ten.

Complexity

Brute force

Time

O(n²)

Every number is paired with every number after it: about n × n ÷ 2 checks.

Space

O(1)

Just the two loop counters.

Hash map (week 1's Two Sum)

Time

O(n)

One pass, each lookup takes about one step.

Space

O(n)

The map may end up holding almost every number.

Two pointers

Time

O(n)

Each step moves one pointer one place inward, so after at most n − 1 steps they meet.

Space

O(1)

Only left, right and the sum, no matter how long the list is. That's what the sorted order buys us.

Common mistakes and edge cases

What to say out loud:

  1. “The list is sorted, so I don’t need a hash map.”
  2. “Pointers at both ends. If the sum is too small, the left number can’t work with anyone, so I move left. If it’s too big, I move right.”
  3. “Each step rules out one number, so it’s O(n) time and O(1) space.”
  4. Remember the 1-based answer.

Likely follow-up questions:

  • “Why is it safe to throw a number away?” Use the argument from the dry run: the left number already had its best possible partner (the biggest one) and still fell short.
  • “What if the input wasn’t sorted?” Then the hash map from week 1’s Two Sum is the right tool: O(n) time, O(n) space.
  • “What about three numbers?” That’s 3Sum: fix one number and run this exact two-pointer loop on the rest.

Related problems:

  • Two Sum (week 1): the unsorted version, solved with a hash map.
  • 3Sum: sort first, then this loop inside another loop.
  • Container With Most Water: two pointers from both ends, deciding which side to move.