Two Sum II - Input Array Is Sorted

Difficulty: Medium Source: NeetCode

Problem

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 as an integer array [index1, index2] where 1 <= index1 < index2 <= numbers.length.

There is exactly one solution, and you may not use the same element twice.

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

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

Example 3: Input: numbers = [-1,0], target = -1 Output: [1,2]

Constraints:

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order
• Exactly one solution exists

Prerequisites

Before attempting this problem, you should be comfortable with:

• Two Sum (LeetCode 1) — the unsorted variant solved with a hash map
• Sorted Arrays — leveraging sorted order to make directional decisions
• Two Pointers — binary search intuition applied to a pair search

1. Brute Force

Intuition

Try every pair of indices and check whether their values sum to target. Since the problem guarantees exactly one answer, we’ll always find it — we’re just doing a lot of unnecessary work checking pairs that can’t possibly work.

Algorithm

1. For i from 0 to len(numbers) - 2:
   • For j from i + 1 to len(numbers) - 1:
     • If numbers[i] + numbers[j] == target: return [i + 1, j + 1].

Solution

def twoSum(numbers, target):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
    return []


print(twoSum([2, 7, 11, 15], 9))   # [1, 2]
print(twoSum([2, 3, 4], 6))        # [1, 3]
print(twoSum([-1, 0], -1))         # [1, 2]

Complexity

• Time: O(n²)
• Space: O(1)

2. Two Pointers

Intuition

Because the array is sorted, we can make smart moves instead of checking everything. Start with left at the smallest element and right at the largest. If their sum equals target, we’re done. If the sum is too small, we need a bigger number — move left rightward to get a larger value. If the sum is too large, we need a smaller number — move right leftward. Each step eliminates one candidate, so we find the answer in a single pass.

Algorithm

1. Initialize left = 0, right = len(numbers) - 1.
2. While left < right:
   • Compute total = numbers[left] + numbers[right].
   • If total == target: return [left + 1, right + 1].
   • If total < target: increment left.
   • If total > target: decrement right.

Solution

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 []


print(twoSum([2, 7, 11, 15], 9))   # [1, 2]
print(twoSum([2, 3, 4], 6))        # [1, 3]
print(twoSum([-1, 0], -1))         # [1, 2]

Complexity

• Time: O(n)
• Space: O(1)

Common Pitfalls

Forgetting the 1-indexed output. The array is 0-indexed in Python but the problem wants 1-indexed answers. Add 1 to both left and right before returning.

Using a hash map (Two Sum style) when O(1) space is required. The hash map approach from the original Two Sum works here too and runs in O(n), but uses O(n) extra space. The two-pointer approach is better because the sorted order gives us direction for free.

Moving both pointers after a mismatch. Only move the pointer that makes the sum closer to target. Moving both simultaneously can skip the correct pair.