Day 3 Leet code series, today we will be picking the problem two sum II – Array is Sorted (https://leetcode.com/problems/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[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] 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].

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        int i=0, j=numbers.size()-1;
        while(i < j){
            if(numbers[i]+numbers[j] == target){
                res.push_back(i+1);
                res.push_back(j+1);
                return res;
            }
            else if(numbers[i]+numbers[j] > target){
                j--;
            }
            else i++;
        }
        return res;
    }
};

Explaination:

1. We will create a res array which will be the output.
2. We will be maintaining two pointer, one will be at the starting and other at the end.
3. If sum of array[i] and array[j] is greater than the the target then we will decrease the j by j–.
4. And if sum of array[i] and array[j] is less than the target then we will increment i by i++.
5. And if sum of array[i] and array[j] is equal to the target then we will return the indices by pushing into the res.