Two Sum II - Input Array Is Sorted medium

Problem Statement

Given a 1-indexed array of integers numbers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where answer[0] < answer[1].

You may assume that each input would have exactly one solution and you may not use the same element twice.

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[1] + numbers[2] == 6, we return [1,3].

Steps:

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

2. Summation: Calculate the sum of the elements at the left and right pointers: sum = numbers[left] + numbers[right].

3. Comparison:

   • If sum equals the target, return the 1-indexed indices [left + 1, right + 1].
   • If sum is less than the target, increment left to consider a larger number.
   • If sum is greater than the target, decrement right to consider a smaller number.

4. Iteration: Continue steps 2 and 3 until the pointers cross (left > right). If the loop completes without finding a solution, it indicates no solution exists (although the problem statement guarantees a solution).

Explanation:

The algorithm leverages the sorted nature of the input array. By using two pointers starting from opposite ends, we efficiently search for the pair that sums to the target. If the sum is too small, we move the left pointer to a larger number. If the sum is too large, we move the right pointer to a smaller number. This approach avoids unnecessary comparisons and achieves linear time complexity.

Code:

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        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-indexed
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        // Should not reach here as the problem guarantees a solution.
        return new int[] { -1, -1 }; 
    }
}

Complexity:

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array at most once using the two pointers.
• Space Complexity: O(1). We use only a constant amount of extra space to store the pointers and the result.