← DSA Atlas
Dedicated problem page · #167

Two Sum II – Input Array Is Sorted

MediumTwo PointersOpposite-end pointers on a sorted arrayTwo pointers (converging)
Solve on LeetCode ↗
167
MediumTwo PointersTwo pointers (converging)Opposite-end pointers on a sorted array

Two Sum II – Input Array Is Sorted

Given a 1-indexed array numbers sorted in non-decreasing order, find two numbers that add up to a specific target. Return their 1-based indices [index1, index2] with index1 < index2. Exactly one solution exists, each element may be used once, and you must use only constant extra space.

Open official problem prompt ↗
In plain English

Locate the unique pair of sorted values summing to target and report their 1-based positions using no extra data structure.

Picture it like this

Two people stand at the low and high ends of a sorted number line and adjust: if their combined value is too small the low person steps up, if too big the high person steps down, converging on the exact total.

Example
Input
numbers = [2, 7, 11, 15], target = 9
Output
[1, 2]
Why
numbers[1] + numbers[2] = 2 + 7 = 9, reported with 1-based indices.
Constraints
2 <= numbers.length <= 3 * 10^4-1000 <= numbers[i] <= 1000numbers is sorted in non-decreasing order-1000 <= target <= 1000Exactly one valid answer exists
Pattern lesson

See the pattern, then code

Opposite-end pointers on a sorted array
Recognition clue

A pair-sum question on an already-sorted array with an O(1) space requirement is the textbook cue for opposite-end two pointers instead of a hash map.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. The sorted order lets the sum steer the search: if the current pair sums too low, only a larger left value can help, so move left inward; if too high, move right inward.

New words, made simpleKnow these before the algorithm
1-indexed
Positions are counted from 1, so the stored 0-based indices are reported plus one.
Monotonic sum
Moving lo right can only increase the sum; moving hi left can only decrease it.
Constant space
Only a fixed number of scalar variables are used, regardless of input size.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Hash map of complements

Correct but ignores the sorted input and violates the O(1) space requirement.

For each value store it in a map and look up target minus it.

Time O(n)Space O(n)
Binary search per element

Constant space but slower than a linear two-pointer sweep.

For each index, binary-search for its complement in the rest of the array.

Time O(n log n)Space O(1)
Best choiceConverging two pointers

Linear time and constant space, exploiting the sortedness fully.

Use the sorted order to move lo or hi based on whether the current sum is below or above target.

Time O(n)Space O(1)
The rule we keep true

Invariant

If a valid pair exists, it always lies within the current [lo, hi] window; no discarded index could belong to the answer.

Why this is correct

Reasoning

When numbers[lo] + numbers[hi] < target, numbers[lo] paired with anything at or below hi is still too small, so lo cannot be part of any solution and is safely dropped. Symmetrically, an over-target sum eliminates hi. Each step removes exactly one index that cannot be in the answer, so the guaranteed pair survives until lo and hi land on it.

The algorithm in three movesSay these aloud before coding
1Set lo at the first index and hi at the last

lo=0 hi=3 -> 2+15=17 > 9, hi=2

2Compute s = numbers[lo] + numbers[hi]

lo=0 hi=2 -> 2+11=13 > 9, hi=1

3If s == target, return [lo+1, hi+1]

lo=0 hi=1 -> 2+7=9, return [1,2]

4If s < target, increment lo; if s > target, decrement hi

5Repeat until the pair is found

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
20
71
112
153
1 · Readnumbers[0]=2, numbers[3]=15
2 · Ask2 + 15 vs 9?
3 · Update statelo=0 hi=3
4 · Result17 > 9, decrement hi to 2
Key takeaway

The window shrinks from the right as sums that exceed the target pull hi inward.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Anchor both ends

    lo at the smallest value, hi at the largest, so their sum spans the widest range.

  2. 2
    Lines 4-5Evaluate the current sum

    s is recomputed each iteration from the two ends of the shrinking window.

  3. 3
    Lines 6-7Success case

    On an exact match return 1-based indices by adding one to each pointer.

  4. 4
    Lines 8-11Steer the pointers

    A low sum raises the floor (lo += 1); a high sum lowers the ceiling (hi -= 1).

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Two-element array that is itself the answer
  • Negative numbers combining to reach target
  • Target equal to the sum of the two smallest or two largest values
  • Duplicate values where the pair uses two equal numbers
!

Common beginner mistakes

  • Returning 0-based indices and forgetting the +1 offset
  • Using lo <= hi and pairing an element with itself
  • Reaching for a hash map and needlessly using O(n) space despite the sorted input
  • Moving the wrong pointer when the sum is off-target
Check your understanding

When the current sum exceeds the target, why is it safe to discard the hi element entirely?

More in Two Pointers

#153SumSorted two-pointer scan around a fixed anchor#11Container With Most WaterConverging pointers on a width-vs-height tradeoff#184SumTwo fixed anchors plus a sorted two-pointer inner scan#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#31Next PermutationFind pivot, swap successor, reverse suffix#42Trapping Rain WaterConverging pointers tracking left/right maxima