Two Sum II - Input Array Is Sorted

Problem Description

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.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only O(1) extra space.

Examples

Constraints

• 2 <= numbers.length <= 3 * 10⁴
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Moving Inward on Sorted Sums

Because the input array is sorted, we can exploit this property to search for the target sum in O(1) space. Set a left pointer at the start of the array and a right pointer at the end. Compute their sum. If the sum matches the target, we have found the solution. If the sum is smaller than the target, we must increase our sum by moving the left pointer to the right. If the sum is larger than the target, we must decrease our sum by moving the right pointer to the left.

Solution 1: Left and Right Two Pointers

Exploit the sorted property of the array to search inward from both ends.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1}; // 1-indexed conversion
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        left = 0
        right = len(numbers) - 1
        while left < right:
            curr_sum = numbers[left] + numbers[right]
            if curr_sum == target:
                return [left + 1, right + 1]  # 1-indexed conversion
            elif curr_sum < target:
                left += 1
            else:
                right -= 1
        return [-1, -1]

#include <vector>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& numbers, int target) {
        int left = 0;
        int right = numbers.size() - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1}; // 1-indexed conversion
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return {-1, -1};
    }
};

Complexity Analysis

• Time Complexity: O(n) since each step moves at least one pointer closer to the other, checking at most n elements.
• Space Complexity: O(1) auxiliary space as the search is performed in place without any extra data structures.

Where It Breaks

If the input array is not sorted, this two-pointer convergence logic fails because moving pointers does not guarantee a predictable increase or decrease in the sum. Under those conditions, a hash map is required, which increases space complexity to O(n).

Common Mistakes

• Incorrect index mapping: Returning 0-indexed values instead of 1-indexed values. You must add 1 to the index pointers before returning the result.
• Pointer overlap: Using the loop condition left <= right which is incorrect because we cannot use the same element twice.

Frequently Asked Questions

Why is this solution better than a hash map? A hash map solution takes O(n) space to store element lookups, whereas this two-pointer solution takes O(1) space, making it much more memory efficient.

Is it possible that no solution exists? No, the problem constraints guarantee that exactly one valid solution always exists in the input array.

← All Problems