Two Sum II - Input Array Is Sorted

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. 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 constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

2 <= numbers.length <= 3 * 10^4
-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.

Solution

Approach: Two Pointers

The key insight is to leverage the sorted nature of the array using two pointers. Start with one pointer at the beginning and one at the end. If the sum is too small, move the left pointer right to increase the sum. If the sum is too large, move the right pointer left to decrease the sum.

This approach is optimal because the array is sorted, allowing us to make intelligent decisions about which pointer to move based on the current sum.

Implementation

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1

        while left < right:
            current_sum = numbers[left] + numbers[right]

            if current_sum == target:
                # Return 1-indexed positions
                return [left + 1, right + 1]
            elif current_sum < target:
                # Sum too small, need larger number
                left += 1
            else:
                # Sum too large, need smaller number
                right -= 1

        return []  # Should never reach here given constraints

Alternative (Binary Search for Each Element):

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            complement = target - numbers[i]

            # Binary search for complement in remaining array
            left, right = i + 1, len(numbers) - 1

            while left <= right:
                mid = (left + right) // 2
                if numbers[mid] == complement:
                    return [i + 1, mid + 1]
                elif numbers[mid] < complement:
                    left = mid + 1
                else:
                    right = mid - 1

        return []

Complexity Analysis

Time Complexity: O(n) for the two-pointer approach, where n is the length of the array. We traverse the array at most once. The binary search approach is O(n log n).
Space Complexity: O(1) for both approaches. We only use a constant amount of extra space.

Key Insights

Exploit Sorted Property: Unlike the original Two Sum problem, we can’t use a hash map here (would violate O(1) space), but we can use the sorted property with two pointers for an elegant O(n) solution.
Greedy Pointer Movement: When the sum is too small, we know moving left pointer right will only increase the sum (array is sorted). Similarly, moving right pointer left will only decrease the sum.
1-Indexed Return: Remember to add 1 to both indices before returning, as the problem uses 1-based indexing.
Guaranteed Solution: Since the problem guarantees exactly one solution exists, we don’t need to handle the case where no solution is found (though we include it for completeness).
Two Pointers vs Binary Search: The two-pointer approach is simpler and more efficient (O(n) vs O(n log n)) than using binary search for each element.