Algorithm

Two Sum II - Input Array Is Sorted

Two Pointer Pattern

Two Sum II - Input Array Is Sorted

Given a 1-indexed array numbers that is already sorted in non-decreasing order, find the two numbers that add up to a given target. Return their positions as a two-element array [index1, index2] with 1 <= index1 < index2 <= numbers.length — the answer is 1-indexed, not 0-indexed. Exactly one pair is guaranteed to add up to target, and you may not use the same element twice. Solve it using O(1) extra space (beyond the output).

CONSTRAINTS
  • 2 <= numbers.length <= 3 × 10⁴
  • Array is sorted in non-decreasing order
  • Exactly one solution exists
  • Output positions are 1-indexed
  • Must use O(1) extra space
EXAMPLE 1
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
2 + 7 = 9, and those sit in the 1st and 2nd positions.
EXAMPLE 2
Input: numbers = [2,3,4], target = 6
Output: [1,3]
2 + 4 = 6. The 3 in the middle is not needed.
EXAMPLE 3
Input: numbers = [-3,-1,0,2,5], target = -1
Output: [2,3]
-1 + 0 = -1. Negative numbers still obey the sorted order, so the same reasoning applies.
Are the returned positions 0-based or 1-based?
1-based. The two smallest valid positions are 1 and 2, not 0 and 1.
Is a solution always guaranteed?
Yes — exactly one pair adds up to the target, so you never have to handle a 'not found' case.
Can the same element be used twice?
No. The two positions must be different, which the left < right condition enforces automatically.
Can the array contain duplicates or negative numbers?
Yes to both. It is non-decreasing (duplicates allowed) and values may be negative; the sorted-order argument holds regardless.

We are handed a sorted array and asked to find the two numbers that add up to target, then return their (1-based) positions. It looks a lot like the original Two Sum — but there the array was in random order, and the trick was a hash map that remembered numbers as we went. Here the array is sorted, and that one extra fact unlocks something cleaner and cheaper.

The blunt way, ignoring the sorted order

You could just try every pair: fix the first number, then scan everything after it for a partner that completes the target. That is two nested loops — about N²/2 pairs — so O(N²) time. It also completely wastes the gift the problem gave us. The numbers are in order, smallest to largest, and this approach never once uses that.

python
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[i] + nums[j] == target:
            return [i + 1, j + 1]
Let the sum steer which end you drop

This is the converging two-pointer walk from Valid Palindrome — one marker at each end, moving inward — but with a smarter rule for which end to move. Put left on the first (smallest) number and right on the last (largest). Add them up and compare to the target:

- If the sum is too big, we need to make it smaller. The only lever that lowers the sum is to trade the big number for a smaller one, so step right left.
- If the sum is too small, we need it bigger, so step left right to a larger number.
- If the sum is exactly right, we found the pair — return the two positions.
python
left, right = 0, len(nums) - 1
while left < right:
    s = nums[left] + nums[right]
    if s == target:
        return [left + 1, right + 1]   # 1-indexed positions
    elif s < target:
        left += 1                      # too small — grow the sum
    else:
        right -= 1                     # too big — shrink the sum
Why dropping that end is provably safe

The whole thing rests on one argument, so let's actually make it. Suppose nums[left] + nums[right] is too big. Ask: could nums[right] still be part of the answer, paired with some other number? Its partner would have to be one of the numbers between left and right. But nums[left] is the smallest of those — everything else is at least as large. So if even the smallest partner already overshoots the target, every other partner overshoots too. nums[right] can never reach the target with anyone. It is useless, and we can discard it forever by stepping right inward. The mirror argument works when the sum is too small: nums[left] paired with the largest available (nums[right]) still falls short, so it falls short with everyone, and we drop it by stepping left inward. Each step removes exactly one number that we have proven cannot be in the answer — which is why one clean pass finds the pair. The invariant, in plain words: the answer, if it involves any number still inside the leftright window, is still findable there; nothing we discarded could have been part of it.

Worked example:numbers = [2, 7, 11, 15], target = 9
- left=0 (2), right=3 (15). Sum 17 > 9 — too big, so 15 can't work with anyone. right→2.
- left=0 (2), right=2 (11). Sum 13 > 9 — still too big. right→1.
- left=0 (2), right=1 (7). Sum 9 — exactly the target. Return [1, 2] (the 1-based positions).
Filling the converging skeleton

Drop this onto the three-slot template from Valid Palindrome. (a) What we read from the two ends: their sum. (b) Which pointer to move: sum too small → left in, too big → right in, equal → done. (c) What to record: nothing until we hit the target, then the two positions. The one and only reason we can decide which end to move is that the array is sorted — order is what turns "the sum is too big" into "so move the big end." Take the sorting away and this steering rule becomes meaningless: in an unsorted array a bigger sum tells you nothing about where a fixing value might sit, and you would be back to a hash map. That is the recognition signal to carry forward — a sorted array plus a question about a pair that hits some target value almost always means this exact inward walk. Next, in 3Sum, we reuse it verbatim as the inner engine, after pinning down one number first.

Interactive Strategy Visualization

Two Sum II Visualization

Converging pointers on a sorted array

LEFT
2
7
11
RIGHT
15
Left Value
2
+
Right Value
15
=
Current Sum
17
TARGET
9

Crucial Concept

  • Monotonic Sum: Moving 'Left' right increases sum. Moving 'Right' left decreases sum.
  • Deterministic: At any step, we know exactly which pointer to move based on the sum comparison.
  • No Backtracking: Pointers only move in one direction (inward), guaranteeing O(N).
LOGICSTEP 1/4
The search begins! We place our pointers at the very ends of our sorted collection: 2 and 15. Together, they sum to 17—way too large for our target of 9!
Decision: Move ← Right
TIP

Pattern Recognition

Whenever you need to find a pair in a sorted array, always consider the Two Pointer approach. It almost always beats the O(N) hash map approach in space complexity (O(1) vs O(N)).

O(N²) Brute Force
O(N log N) Binary Search Per Element
O(N) Time · O(1) Space Converging Scan