Two Sum II - Input Array Is Sorted medium

Problem Statement

Given a sorted array of integers numbers and an integer target, find two distinct indices i and j (where i < j) such that numbers[i] + numbers[j] == target. You may assume that each input would have exactly one solution and you may not use the same element twice. Return the indices of the two numbers, i and j, in the form of an array [i, j] (1-based indexing).

Example 1

Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: Because numbers[0] + numbers[1] == 9, we return [1, 2].

Example 2

Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: Because numbers[0] + numbers[2] == 6, we return [1, 3].

Steps

1. Two Pointers Approach: Utilize two pointers, left and right, initialized to the beginning and end of the array, respectively.

2. Iteration: Iterate while left < right.

3. Sum Calculation: Calculate the sum currentSum = numbers[left] + numbers[right].

4. Comparison:

   • If currentSum == target, the desired pair is found. Return [left + 1, right + 1] (1-based indexing).
   • If currentSum < target, increment left to increase the sum.
   • If currentSum > target, decrement right to decrease the sum.

Explanation

The algorithm leverages the sorted nature of the input array. By using two pointers, one starting from the beginning and the other from the end, we efficiently search for the pair that sums to the target. If the sum is less than the target, we move the left pointer to a larger element; if the sum is greater than the target, we move the right pointer to a smaller element. This approach avoids redundant checks and guarantees finding the solution in linear time.

Code

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int currentSum = numbers[left] + numbers[right];

            if (currentSum == target) {
                return new int[] {left + 1, right + 1}; // 1-based indexing
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }

        return new int[] {}; // Should not reach here if a solution exists
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We perform a single pass through the array using the two-pointer approach.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space to store the pointers and the result.