~/leetcode$cat167. Two-Sum-II-Input-Array-Is-Sorted

An extension to the classic two sum question but the input array is sorted and we want to use constant space (the solution to the original two sum used a hashset which requires O(n) space).

Here, we can use the fact that the input list is sorted in order to solve this problem in constant space. If we instantiate our left and right pointers on either side of the list (one pointer at the start and the other pointer at the end) and use the sum of the two numbers they are pointing to as our initial sum, we can do the following while the left pointer is still smaller than the right pointer:

• if the current sum is larger than the target sum, we move our right pointer to the left. This will make the sum smaller as the input array is sorted (so if we are using the n-th element, we use the n - 1th element instead - n - 1th element is guaranteed to be smaller than the nth element)
• similarly, if the current sum is smaller than the target sum, we move our left pointer to the right. This will make the sum larger - by the same logic as above
• if the current sum is equal to the target sum, we can return the indexes that the two pointers are pointing at (make sure to add one because they want it 1-indexed for some reason).

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

        while (left < right) {
            int currSum = numbers[left] + numbers[right];
            if (currSum == target) {
                return {left + 1, right + 1};
            }

            if (currSum > target) {
                --right;
            } else {
                ++left;
            }
        }

        return {-1, -1};
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Time Taken: 3m 08s