loading

Two Sum II - Input Array Is Sorted — Step-by-Step Visualization

mediumLeetCode #167ArrayTwo PointersBinary Search

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. Let these two numbers be `numbers[index1]` and `numbers[index2]` where `1 <= index1 < index2 <= numbers.length`. Return the indices of the two numbers, `index1` and `index2`, added by one as an integer array `[index1, index2]` of length 2.

Algorithm Pattern

Two Pointers on Sorted Array

Key Idea

Since the array is sorted, we can use two pointers: `left` at the beginning and `right` at the end. If their sum is greater than the target, we must decrease the sum by moving `right` inward. If the sum is smaller, we increase it by moving `left` inward.

Step-by-Step Approach

  1. Initialize `left = 0` and `right = len(numbers) - 1`.
  2. Calculate the current sum: `numbers[left] + numbers[right]`.
  3. If `sum == target`, return `[left + 1, right + 1]`.
  4. If `sum > target`, decrement `right`.
  5. If `sum < target`, increment `left`.
  6. Repeat until pointers meet.

Common Gotchas

  • The problem uses 1-based indexing for the result.
  • Because the array is sorted, moving pointers inward based on sum comparison is guaranteed to find the unique solution if it exists.

Related Problems

← All problems