Two Sum II - Input Array Is Sorted

PracticeNeetCode ↗LeetCode ↗

Given a 1-indexed array of integers numbers already sorted in non-decreasing order, find two numbers that add up to target and return their indices (1-indexed) as an array of two integers.

Example

Key Pointers

• Sorted input means two pointers can replace the hashmap used in the plain Two Sum problem — no extra space needed.
• If the current pair's sum is too small, only moving the left pointer right can help; if too large, only moving the right pointer left can help.
• Because the array is sorted, every pointer move provably narrows the search space — nothing skipped could have been the answer.

Step-by-Step Analysis

1. Set left = 0, right = len(numbers) - 1.
2. While left < right: compute total = numbers[left] + numbers[right].
3. If total == target, return [left + 1, right + 1] (converted to 1-indexed).
4. If total < target, move left forward; if total > target, move right backward.

Complexity

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

Code

def twoSum(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

Code Explanation

How the solution above works, piece by piece.

1. Start with the smallest (left = 0) and largest (right = n − 1) numbers.
2. total == target: found. The problem uses 1-based indices, hence left + 1, right + 1.
3. total < target: the sum must grow. Only moving left right can do that, because the array is sorted.
4. total > target: the sum must shrink, so move right left. No pair is ever skipped that could have worked.
5. Each step moves one pointer, so at most n steps: O(n) time, O(1) space (no hash map needed, unlike the unsorted Two Sum).

Visual Walkthrough

Running it on numbers = [2, 7, 11, 15], target = 9:

Video Explanation

NeetCode — LeetCode 167