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]

Steps:

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

2. Sum and Compare: Calculate the sum of the elements at the left and right pointers.

3. Adjust Pointers:

   • If the sum is equal to the target, return the indices left + 1 and right + 1 (1-indexed).
   • If the sum is less than the target, increment the left pointer to consider a larger number.
   • If the sum is greater than the target, decrement the right pointer to consider a smaller number.

4. Continue until Solution Found: Repeat steps 2 and 3 until a solution is found. Since there's guaranteed to be exactly one solution, the loop will terminate.

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 increase the sum. If the sum is too large, we move the right pointer to decrease the sum. This approach avoids unnecessary comparisons and achieves a linear time complexity.

Code:

#include <vector>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& numbers, int target) {
        int left = 0;
        int right = numbers.size() - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1}; // 1-indexed return
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return {}; //Should not reach here as problem guarantees a solution.
    }
};

Complexity:

• Time Complexity: O(N), where N is the length of the input array. We perform a single pass through the array using two pointers.
• Space Complexity: O(1). We use only a constant amount of extra space to store the pointers and the result.