Coding Interview PatternsTwo Sum II - Input Array Is Sorted
MediumTwo Pointers

Two Sum II - Input Array Is Sorted

Explanation & Solution

Practice Problem

Description

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

You may not use the same element twice. Your solution must use only constant extra space.

Input:numbers = [2, 7, 11, 15], target = 9
0
2
1
7
2
11
3
15
Output:[1, 2]
0
1
1
2

Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Constraints

  • 2 <= numbers.length <= 3 * 10⁴
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order
  • -1000 <= target <= 1000
  • There is exactly one solution

Approach

Two Pointers pattern

1. Initialize Two Pointers

  • Set left = 0 (start of array)
  • Set right = numbers.length - 1 (end of array)
  • Since the array is sorted, we can exploit ordering with two pointers

2. Loop While Pointers Haven't Crossed

  • Continue while left < right
  • This guarantees we never use the same element twice

3. Compute the Current Sum

  • Calculate sum = numbers[left] + numbers[right]
  • Compare this sum against the target

4. Check If Sum Equals Target

  • If sum === target:
  • Return [left + 1, right + 1]
  • We add 1 because the problem uses 1-indexed positions

5. Sum Too Small — Move Left Pointer Right

  • If sum < target:
  • Increment left++
  • Moving left forward increases the sum because the array is sorted

6. Sum Too Large — Move Right Pointer Left

  • If sum > target:
  • Decrement right--
  • Moving right backward decreases the sum because the array is sorted

7. Return Result

  • The loop always finds the answer (guaranteed by constraints)
  • Return an empty array as a fallback if no solution is found

Key Insight

  • The core idea is that in a sorted array, the two-pointer technique lets us efficiently narrow the search space: if the sum is too small we need a larger number (move left pointer right), and if the sum is too large we need a smaller number (move right pointer left)
Time
O(n)each pointer moves at most n times total
Space
O(1)only two pointer variables are used

Visualization

Input:
[2, 7, 11, 15], target = 9
2071112153
—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone
5 steps

Solution Code

Next
Valid Palindrome