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)
This is Two Sum from week 1 with two changes:
- The list
numbersis sorted: every number is at least as big as the one before it, like[1, 3, 4, 6, 8]. - 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.
- 10
- 31
- 42
- 63
- 84
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.
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:
- 10
- 31
- 42
- 63
- 84
Pause and think
Cross off 8. The smallest number still in play is 3, and even 3 + 8 is too
big. Every other partner for 8 is bigger than 3, so its sum would be bigger
still. 8 can’t be in the answer, so right moves left to 6.
Every comparison crosses off one number for good. That’s why we never need to go back.
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
- 10
- 31
- 42
- 63
- 84
- 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.
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 []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.
Pattern
Converging two pointers
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”
- Put
lefton index 0 (the smallest number) andrighton the last index (the biggest). - Add them up:
sum = numbers[left] + numbers[right]. - If
sumequalstarget, return[left + 1, right + 1](positions count from 1). - If
sumis too small, the left number is useless: moveleftone step right. - If
sumis too big, the right number is useless: moverightone step left. - Repeat while
leftis smaller thanright.
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
- 10
- 31
- 42
- 63
- 84
- 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.
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.
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
totalbecausesumis 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
leftup 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
rightdown 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.
numbers = [1, 3, 4, 6, 8], target = 10:
| step | left | right | numbers[left] + numbers[right] | compare | move |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 1 + 8 = 9 | < 10 | left → 1 (cross off 1) |
| 2 | 1 | 4 | 3 + 8 = 11 | > 10 | right → 3 (cross off 8) |
| 3 | 1 | 3 | 3 + 6 = 9 | < 10 | left → 2 (cross off 3) |
| 4 | 2 | 3 | 4 + 6 = 10 | = 10 | return [3, 4] |
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.
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.
What to say out loud:
- “The list is sorted, so I don’t need a hash map.”
- “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.”
- “Each step rules out one number, so it’s O(n) time and O(1) space.”
- 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.