Two Sum II: Why Sorted Input Turns a Hash Map Into Two Pointers
Solve Two Sum II with opposing two pointers — O(n) time, O(1) space on a sorted array. Intuition, JavaScript code, a full walkthrough, and pitfalls.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Two Sum II looks like a rerun. Same pair-sum question as the original Two Sum, same "exactly one solution" guarantee — so why does LeetCode list it as a separate problem? Because one word changed everything: sorted.
That single property unlocks the second great pair-finding pattern: opposing two pointers. Where Two Sum trades memory for time with a hash map, Two Sum II gets O(n) time with zero extra memory — and the problem statement enforces it by demanding constant extra space. If you reach for the hash map here, you've technically solved it and strategically missed the point.
The squeeze mechanic you learn here — pointers at opposite ends, each comparison permanently eliminating one candidate — is the engine behind 3Sum, Container With Most Water, and Trapping Rain Water. This is the cleanest place to learn it.
The problem
Given a 1-indexed array numbers, sorted in non-decreasing order, and an integer target, return the indices of the two numbers that add up to target. Exactly one solution exists, you may not use the same element twice, and your algorithm must use only constant extra space.
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2] // numbers[1] + numbers[2] = 2 + 7 = 9 (1-indexed)Three constraints shape the solution:
- Sorted input — the big hint. Order is information; an algorithm that ignores it is leaving speed on the table.
- O(1) extra space — this outlaws the hash map from classic Two Sum, which stores up to n entries.
- 1-indexed output — a pure formatting trap. Your loop runs on 0-based indices; the answer must add 1 to each.
The brute force baseline
Check every pair, exactly as you would on an unsorted array:
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];
}
}
return [];
}This is O(n²) and treats the sorted array as if it were random noise. There's a smarter-but-still-not-optimal middle step: for each element, binary search the rest of the array for its complement. That uses the sort order and drops to O(n log n) — n outer iterations, each paying a log n search. Better, but it still re-searches from scratch for every element, learning nothing from the previous iteration. The optimal solution never repeats work.
The key insight: every comparison eliminates a candidate forever
Place one pointer at each end of the array: left at the smallest value, right at the largest. Their sum can now be steered. Too small? Move left right — in a sorted array, that's guaranteed to increase the sum. Too big? Move right left — guaranteed to decrease it.
The part interviewers actually probe is why discarding is safe. Suppose numbers[left] + numbers[right] < target. Then numbers[left] is useless forever — numbers[right] is the largest value still in play, and even that partner was too small. No element between the pointers can rescue left, so we abandon it permanently with left++. Symmetrically, when the sum is too big, numbers[right] can't pair with anything: numbers[left] is the smallest remaining value and even that overshot. So right-- is safe.
Each iteration retires one index for good, so the pointers meet after at most n − 1 comparisons. Since a solution is guaranteed and we never discard an index that could still participate in it, the pointers must land on the answer before crossing. That exchange argument — "the discarded element had its best possible partner and still failed" — is the whole pattern.
The optimal solution
This is exactly the algorithm the interactive visualizer steps through:
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];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}Three details worth internalizing:
- The loop condition is
left < right, strictly. If the pointers could meet (<=), the same element would pair with itself — the exact bug the "may not use the same element twice" rule forbids. - The return is
[left + 1, right + 1], converting 0-based loop indices to the 1-indexed answer in one place, at the last possible moment. - Exactly one pointer moves per iteration, and always by one step. Two variables, no allocations — genuinely O(1) space.
Walkthrough: numbers = [1, 3, 4, 5, 7, 10], target = 9
| Step | left | right | numbers[left] + numbers[right] | vs target | Move |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 1 + 10 = 11 | 11 > 9 | right-- |
| 2 | 0 | 4 | 1 + 7 = 8 | 8 < 9 | left++ |
| 3 | 1 | 4 | 3 + 7 = 10 | 10 > 9 | right-- |
| 4 | 1 | 3 | 3 + 5 = 8 | 8 < 9 | left++ |
| 5 | 2 | 3 | 4 + 5 = 9 | 9 = 9 | return [3, 4] |
Watch the steering: every overshoot pulls right down to a smaller value, every undershoot pushes left up to a larger one. The sum oscillates around the target while the window collapses — 11, 8, 10, 8, 9. Five comparisons on a six-element array; brute force could burn up to 15.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force | O(n²) | O(1) | every pair, ignores the sort |
| Hash map (Two Sum classic) | O(n) | O(n) | fast, but stores up to n entries — violates the space constraint |
| Binary search per element | O(n log n) | O(1) | n independent complement searches, no learning between them |
| Opposing two pointers | O(n) | O(1) | each comparison permanently eliminates one index |
Two pointers wins on both axes at once. The visualizer's comparison panel makes the gap concrete: on the walkthrough input, the pointers finish in 5 moves while binary search would spend n × log n work re-searching for each element's complement.
Common mistakes
- Returning 0-indexed positions. The answer is
[left + 1, right + 1]. Forgetting the +1 produces off-by-one wrong answers that pass a careless eyeball test. - Looping with
left <= right. Atleft === rightthe element pairs with itself — for[3, 4]and target 6, you'd falsely "find" 3 + 3. Strict<is load-bearing. - Defaulting to the hash map. It runs, but it uses O(n) space against an explicit O(1) constraint, and it signals that you didn't notice the sorted hint. Interviewers set this problem precisely to see if you adapt.
- Moving both pointers after a miss. Only one boundary is proven useless per comparison. Skipping both can jump over the unique answer.
- Skipping the safety argument. "Move left to increase the sum" is the what. The why — the discarded element just failed with its best possible partner — proves correctness, and it's the transferable half of the pattern.
- Assuming duplicates or negatives break it. They don't.
[1, 2, 3, 4, 4, 9]with target 8 lands both pointers on the two 4s; negatives steer identically because sorted order, not sign, drives the moves.
Where this pattern shows up next
Opposing two pointers is a whole family, and this problem is its cleanest member:
- Container With Most Water — the same squeeze, but the elimination argument is about which wall limits the area instead of which value caps the sum.
- Two Sum — the unsorted original, where indices matter and the hash map is the right call. Knowing when each variant applies is the real skill.
- Is Subsequence — the sibling pattern: two pointers marching the same direction through two sequences.
- Find the Index of the First Occurrence in a String — parallel pointers driving substring matching.
To feel the mechanic rather than read it, step through Two Sum II interactively — the sum balance tilts toward the target while the eliminated cells gray out, one comparison at a time.
FAQ
Why does the two pointer approach work on a sorted array?
Because sorted order makes the sum steerable and discards provable. With pointers at both ends, moving left rightward always increases the sum and moving right leftward always decreases it. When the sum is too small, numbers[left] just failed with the largest value still available, so no remaining partner can save it — it's safe to discard. The symmetric argument covers right. Each comparison permanently eliminates one index, so the answer pair is found in at most n − 1 steps.
What is the time and space complexity of Two Sum II?
O(n) time and O(1) space. The two pointers start n − 1 positions apart and move one step closer on every iteration, so the loop runs at most n − 1 times with constant work per step. The only state is two index variables. Brute force is O(n²), and binary-searching each element's complement is O(n log n) — both slower, and the hash map alternative costs O(n) space the problem explicitly forbids.
Why not use the hash map solution from the original Two Sum?
It produces correct pairs but breaks the constant-extra-space requirement, since the map can grow to n entries, and it wastes the strongest hint in the statement: the input is already sorted. Two pointers match the hash map's O(n) time at O(1) space — strictly better here. The hash map remains the right tool when the input is unsorted and original indices must be preserved, which is exactly the classic Two Sum setup.
Why does Two Sum II return 1-indexed positions?
The problem statement defines numbers as a 1-indexed array, so the expected answer for [2, 7, 11, 15] with target 9 is [1, 2], not [0, 1]. Your code still iterates with normal 0-based indices; you convert once at the return with [left + 1, right + 1]. Forgetting that conversion is the single most common wrong-answer submission on this problem.
Does the two pointer solution handle duplicates and negative numbers?
Yes, with no special cases. Duplicates are fine because the algorithm compares sums, not identities — in [1, 2, 3, 4, 4, 9, 56, 90] with target 8, the pointers converge onto the two distinct 4s at different indices. Negatives are fine because the elimination logic depends only on sorted order: in [-5, -3, 0, 2, 4, 6, 8] with target 1, the same squeeze finds −3 + 4 = 1.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.