Two Sum II - Input Array Is Sorted

How it works

Because the array is sorted, we can use two pointers to adjust the sum efficiently.
If the current sum is too big, moving the right pointer left makes the sum smaller.
If the sum is too small, moving the left pointer right makes the sum larger.
This lets us quickly close in on the target without checking every pair.

Steps

1. Initialize two pointers:
   • l = 0 (start)
   • r = len(numbers) - 1 (end)
2. While l < r:
   • Compute curSum = numbers[l] + numbers[r].
   • If curSum > target, move r left to reduce the sum.
   • If curSum < target, move l right to increase the sum.
   • If curSum == target, return [l + 1, r + 1].
3. If no pair matches the target, return an empty list.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Returning 0-Indexed Instead of 1-Indexed Results

The problem explicitly requires 1-indexed positions in the output. A common mistake is returning [i, j] instead of [i + 1, j + 1]. Always double-check the problem requirements for indexing conventions, as returning 0-indexed results will be marked as incorrect.

Not Leveraging the Sorted Property

Since the array is already sorted, the two-pointer approach achieves O(n) time with O(1) space. Using a hash map still works but wastes the sorted property and uses O(n) extra space unnecessarily. While not incorrect, failing to recognize and use the sorted property results in a suboptimal solution.

Moving Both Pointers in the Same Direction

In the two-pointer approach, when the sum is too large you should move the right pointer left, and when the sum is too small you should move the left pointer right. A common error is moving both pointers in the same direction or moving the wrong pointer, which causes the algorithm to miss the valid pair or loop infinitely.

from typing import List

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1

        while l < r:
            curSum = numbers[l] + numbers[r]

            if curSum > target:
                r -= 1
            elif curSum < target:
                l += 1
            else:
                return [l + 1, r + 1]
        return []

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

        while (l < r) {
            int curSum = numbers[l] + numbers[r];

            if (curSum > target) {
                r--;
            } else if (curSum < target) {
                l++;
            } else {
                return { l + 1, r + 1 };
            }
        }
        return {};
    }
};