🧮 Two Sum II – Input Array is Sorted

🔍 Problem Statement

Given a 1-indexed array of integers numbers that is 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, added by one, as an integer array [index1, index2].

• You may not use the same element twice.

• The input is guaranteed to have exactly one solution.

• Your solution must use only constant extra space.

🧾 Example:

Input: numbers = [2,7,11,15], target = 9  
Output: [1,2]
Explanation: The sum of numbers[0] + numbers[1] = 2 + 7 = 9

💡 Intuition

We are told the array is sorted. That’s the key!

Instead of brute force (trying all pairs), we can use a two-pointer technique, which works beautifully on sorted arrays.

The idea:

• One pointer starts at the beginning (left).

• One pointer starts at the end (right).

• Move the pointers inward depending on the sum.

This way, we narrow down the possible pair without using any extra space like a hash map.

🧠 Logic

Step-by-step approach:

1. Initialize two pointers:
   left = 0 (start),
   right = numbers.size() - 1 (end)

2. While left < right:

   • Calculate currentSum = numbers[left] + numbers[right]

   • If currentSum == target, return [left+1, right+1]
     (+1 because the array is 1-indexed)

   • If currentSum < target, move the left pointer rightwards to get a larger sum.

   • If currentSum > target, move the right pointer leftwards to get a smaller sum.

3. If no such pair is found (though problem guarantees one), return {}.

🧑‍💻 C++ Code

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1}; // Return 1-based indices
            }
            else if (sum < target) {
                left++; // Move left pointer to increase sum
            }
            else {
                right--; // Move right pointer to decrease sum
            }
        }
        return {}; // Fallback, though problem guarantees a solution
    }
};

⚙️ Time and Space Complexity

• Time Complexity: O(n)
  (Each element is checked at most once)

• Space Complexity: O(1)
  (Only two pointers used, no extra space)

✅ Why This Works

This works because the array is sorted, allowing us to use a greedy two-pointer approach. If the sum is too small, move the left pointer to a bigger number; if the sum is too big, move the right pointer to a smaller number.

It avoids extra space and checks only necessary combinations.

🔚 Final Thoughts

This is a classic example where knowing the data is sorted allows for major optimization. The two-pointer pattern is one you should remember—it’s very powerful for problems involving sorted arrays or sequences.

problem statement: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/