Faangprep Logo
LoginRegister
Browse Curriculum
Two Pointers
Medium

Two Sum II - Input Array Is Sorted

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.
10 min read
Solve on LeetCode
Examples
Input:numbers = [2,7,11,15], target = 9
Output:[1,2]
Explain:

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

Input:numbers = [2,3,4], target = 6
Output:[1,3]
Explain:

The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Problem Understanding

This is similar to the classic Two Sum, but with two key differences:

  1. The array is already sorted.
  2. You must return 1-based indices.

A brute force approach would be to check every pair, which is O(n²). However, the sorted property allows us to use the Two Pointers technique to solve it in linear time O(n).

Algorithm Strategy

  1. Initialize left at the start (index 0) and right at the end (index n-1).
  2. Calculate current_sum = numbers[left] + numbers[right].
  3. If current_sum == target, we found the pair! Return [left + 1, right + 1].
  4. If current_sum < target, we need a larger sum. Since the array is sorted, moving left to the right increases the sum.
  5. If current_sum > target, we need a smaller sum. Moving right to the left decreases the sum.

Interactive Visualization

Step 1 / 1

Initializing...

1x

The visualization matches target using left and right pointers.

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.