Arrays - Two Sum II, Input Array Is Sorted

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[index₁] and numbers[index₂] where 1 <= index₁ < index₂ <= numbers.length.

Return the indices of the two numbers, index₁ and index₂, added by one as an integer array [index₁, index₂] 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⁴
-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 1 - Using Two pointers

Since the input array numbers is sorted in non decreasing order, and it is guaranteed to have exactly one solution, in this approach, we are going to use two pointers on both ends of array and move them towards eachother to find the pair of numbers that adds upto target.

Implementation steps:

Create two variables left and right, to point to left and right ends of the input array numbers. Initialize them with left = 0 and right = nums.length -1.
Then, loop through elements of numbers using a while loop until left and right don't intersect with each other, compute the sum of elements at left and right indexes, and check the following:
- If sum is equal to target: Then return the indexes (add +1 to the indexes, since the input array is 1-indexed).
- If sum is less than target: Then increment left index by 1, since the sum is less than target.
- If sum is greater than target: Then decrement right index by 1, since the sum is greater than target.

import java.util.Arrays; public class TwoSumII { static int[] twoSumII(int[] numbers, int target) { //since the array is sorted, we can use two pointers: // If sum is greater, move right pointer to left. // If sum is lesser, move left pointer to right. 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 because the input array is 1- indexed } else if (sum < target) { left++; } else { right--; } } return null; } public static void main(String[] args) { System.out.println(Arrays.toString(twoSumII(new int[] {2,7,11,15}, 9))); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input array numbers.
Space complexity: O(1).