167. 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:
Example 2:
Example 3:
Constraints:
- 2 <= numbers.length <= 3 * 104
- -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
The problem states that we must use constant space, therefore, we cannot use a hashmap as we did for the original two sum.
In order to solve this, we can use the fact that it is sorted and there is exactly one solution.
We can use a two-pointer approach to solve this. We initialize two pointers, one on each side of the array and iterate as long as they don't cross eachother. On each iteration, we can check if the two numbers add up to the target, if they do, we return the solution. Otherwise, we check if the result is less than the target; that means we need a larger number, so we increment our left pointer because the array is sorted and we want a larger value. If the result is greater than the target, we want a smaller number, so we decrement the right pointer because, again, the array is sorted and we want a smaller value.
Through this, we are guranteed to find the solution in the iteration because the tests are generated so that there is exactly one solution.
The problem also states that the array is 1-indexed so we want to make sure to increment our index values when returning the solution.
Complexity
Time: O(n)
We iterate over the input array only once.
Space: O(1)
We do not create any additional space.