MediumArrayTwo PointersBinary SearchUpdated Sep 2026

167. Two Sum II - Input Array Is Sorted

Asked at Google, Amazon, Oracle

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

3

Problem

You get an array of integers called numbers that is already sorted in non-decreasing order (each element is greater than or equal to the one before it). You also get a target number.

Find two different elements whose sum equals target. You may not use the same element twice. The tests guarantee that exactly one such pair exists.

Return the positions of those two elements as [index1, index2], where index1 < index2. The positions are 1-indexed, so the first element of the array has position 1, not 0. Your solution must use only constant extra space — no hash map.

Find the pair that hits the target

numbers2 + 7 = 92711150123The answer is the positions of 2 and 7, written as[1,2] in 1-indexed form.
In [2,7,11,15] with target 9, only the values 2 and 7 add up, and they sit at 1-indexed positions 1 and 2.

Constraints

  • ●2 <= numbers.length <= 3 * 10^4
  • ●-1000 <= numbers[i] <= 1000
  • ●numbers is sorted in non-decreasing order
  • ●-1000 <= target <= 1000
  • ●Exactly one valid pair exists in every test case

Examples

Example 1
Inputnumbers = [2,7,11,15], target = 9
Output[1,2]
WhyThe elements at positions 1 and 2 are 2 and 7, and 2 + 7 = 9. No other pair adds up to 9.
Example 2
Inputnumbers = [2,3,4], target = 6
Output[1,3]
Why2 sits at position 1 and 4 sits at position 3, and 2 + 4 = 6. The pair 3 + 3 is not allowed because we cannot reuse the same element.
Example 3
Inputnumbers = [-1,0], target = -1
Output[1,2]
WhyThe only two elements are -1 and 0, and -1 + 0 = -1, so we return their positions 1 and 2.

Asked At

3 companies
CompanyDifficulty
GoogleMediumView all Google questions →
AmazonMediumView all Amazon questions →
OracleMediumView all Oracle questions →

How to Think About It

1

Brute force: check every pair. O(n²). The sorted property allows a much better approach.

2

Two pointers: start with left at index 0 and right at index n-1. The sum of these two is the maximum possible. If sum > target, move right left. If sum < target, move left right.

3

Why it works: in a sorted array, moving the left pointer right increases the sum, and moving the right pointer left decreases the sum. Each step eliminates one element from consideration.

4

Why no hash map is needed: unlike Two Sum I, the array is sorted. Two pointers gives O(n) time and O(1) space, which is better than hash map's O(n) space.

5

Edge cases: exactly one solution guaranteed, no duplicates in valid pairs, 1-indexed output.

Optimal Approach

Step 1: Set left = 0, right = n-1.
Step 2: While left < right:
current_sum = nums[left] + nums[right]
- If current_sum == target: return [left+1, right+1] (1-indexed)
- If current_sum < target: move left right (need larger sum)
- If current_sum > target: move right left (need smaller sum)

The 1-indexed return is important. The problem uses 1-based indexing.

Time: O(n) — each pointer moves at most n times. Space: O(1).

Two pointers squeeze toward the target

numbers2711150123leftrightStart: 2 + 15 = 17, which is too big, so move rightone step left.numbers2711150123leftrightNow 2 + 11 = 13, still too big, so move right leftagain.numbers2711150123leftrightNow 2 + 7 = 9, which matches the target, so return[left+1, right+1] = [1,2].sum < target → left += 1sum > target → right -= 1sum == target → return [left+1, right+1]
left starts at the smallest value, right at the largest. A sum that is too big moves right left; a sum that is too small moves left right.
ComplexityTime O(n)Space O(1)Each pointer moves at most n steps total, and we only keep two index variables.

What Trips People Up in Real Interviews

1

Returning 0-indexed positions. The problem asks for 1-indexed positions. Return [left+1, right+1], not [left, right].

2

Using a hash map. While it works (O(n) time), the two-pointer approach is O(1) space and is the expected solution for a sorted array.

3

Not handling the case where the sum equals the target. When total == target, return immediately. Don't continue searching.

4

Moving both pointers at once. Only move one pointer per iteration. Moving both might skip the valid pair.

5

Confusing this with Two Sum I. That problem uses an unsorted array and requires a hash map. This problem uses a sorted array and two pointers.

Solution Code

O(n) time
def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        elif total < target:
            left += 1
        else:
            right -= 1
    return []

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Two Sum II - Input Array Is Sorted problem?

Given a sorted array of integers and a target, find two numbers that add up to the target. Return their 1-indexed positions. This problem demonstrates the two-pointer technique on sorted data, achieving `O(n)` time without a `hash map`.

How do you solve Two Sum II - Input Array Is Sorted?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Two Sum II - Input Array Is Sorted?

Two Sum II - Input Array Is Sorted is asked at Google, Amazon, Oracle. It is a medium difficulty problem.

What are common mistakes on Two Sum II - Input Array Is Sorted?
  • Returning 0-indexed positions. The problem asks for 1-indexed positions. Return [left+1, right+1], not [left, right].
  • Using a `hash map`. While it works (`O(n)` time), the two-pointer approach is `O(1)` space and is the expected solution for a sorted array.
  • Not handling the case where the sum equals the target. When `total == target`, return immediately. Don't continue searching.
  • Moving both pointers at once. Only move one pointer per iteration. Moving both might skip the valid pair.
  • Confusing this with Two Sum I. That problem uses an unsorted array and requires a `hash map`. This problem uses a sorted array and two pointers.