Skip to content
AI360Xpert
Back to Two Pointers
Medium

Two Sum II (Sorted Array)

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, 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.

Examples

Input:numbers = [2,7,11,15], target = 9
Output:[1,2]
The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Input:numbers = [2,3,4], target = 6
Output:[1,3]
The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Input:numbers = [-1,0], target = -1
Output:[1,2]
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.

Approach

1. **Intuition**: Since the array is sorted, for every number, we can binary search the rest of the array to find its complement (target - number). 2. **Iterate**: Loop through each element `numbers[i]`. 3. **Calculate Complement**: The number we need to find is `target - numbers[i]`. 4. **Binary Search**: Use binary search on the subarray starting from `i + 1` to the end of the array. If the complement is found, return the indices (1-based). 5. **Completion**: If we finish the loop, we return an empty array (though the problem guarantees exactly one solution).

Complexity Analysis

Time Complexity
O(n log n)
Space Complexity
O(1)

This approach is slower than O(n) but satisfies the O(1) space constraint.

Solution.java
class Solution {    public int[] twoSum(int[] numbers, int target) {        for (int i = 0; i < numbers.length; i++) {            int complement = target - numbers[i];                        // Binary search for the complement            int left = i + 1;            int right = numbers.length - 1;                        while (left <= right) {                int mid = left + (right - left) / 2;                if (numbers[mid] == complement) {                    return new int[] { i + 1, mid + 1 }; // 1-based indexing                } else if (numbers[mid] < complement) {                    left = mid + 1;                } else {                    right = mid - 1;                }            }        }                return new int[0];    }}