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.
Key Insights
- The input array is sorted, which allows the implementation of efficient algorithms.
- The problem requires finding two distinct indices that sum up to the target.
- There is exactly one solution guaranteed, simplifying the search process.
- The solution must operate in constant space, meaning no additional data structures can be used.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
The problem can be solved using the two-pointer technique due to the sorted nature of the input array. We can initialize two pointers: one at the beginning (left) and one at the end (right) of the array. By evaluating the sum of the values at these pointers, we can adjust the pointers based on whether the sum is less than, greater than, or equal to the target. If the sum is equal to the target, we return the indices of the two numbers. This approach ensures we only traverse the array once, yielding an optimal solution in linear time.