Two Sum II – Input Array is Sorted

Given an array numbers that is sorted in non-decreasing order and a target target, find two numbers in the array such that they add up to the target.

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

You must return the indices of the two numbers as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.size().

Sample Input and Expected Output:

Input:

numbers = [2, 7, 11, 15]
target = 9

Output:

Indices of the two numbers that add up to the target: [1, 2] // (2 + 7 = 9)

Two Sum Solution in C++:

Since the input array numbers is sorted, we can use a two-pointer approach to find the two numbers that add up to the target. We start with two pointers, left at the beginning of the array and right at the end of the array. We calculate the sum of the elements at these pointers and compare it with the target. Depending on the comparison result, we either move the left pointer to the right or the right pointer to the left until we find the target.

#include <iostream>
#include <vector>

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) {
            // Found the two numbers that add up to the target.
            return {left + 1, right + 1};
        } else if (sum < target) {
            left++; // Increment left pointer for a larger sum.
        } else {
            right--; // Decrement right pointer for a smaller sum.
        }
    }

    // No solution found, return an empty vector.
    return {};
}

int main() {
    std::vector<int> numbers = {2, 7, 11, 15};
    int target = 9;

    std::vector<int> result = twoSum(numbers, target);

    if (!result.empty()) {
        std::cout << "Indices of the two numbers that add up to the target: [";
        for (int index : result) {
            std::cout << index << " ";
        }
        std::cout << "]" << std::endl;
    } else {
        std::cout << "No solution found." << std::endl;
    }

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the solution is O(n), where n is the size of the numbers vector. This is because we use a two-pointer approach, and each element is visited at most once.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The output vector, answer, contains two elements and is not considered in the space complexity analysis since it is part of the function’s return value.