Two Sum II Input Array Is Sorted — LC 167 Two Pointer Pattern Explained

Problem Statement#

Given a 1-indexed array numbers sorted in non-decreasing order, return the 1-indexed positions of two numbers that add up to target. Use only O(1) extra space, and assume exactly one valid answer exists.

Constraints:

• 2 less than or equal to numbers.length less than or equal to 3 times 10 to the 4
• Values in range minus 1000 to plus 1000
• Array is sorted in non-decreasing order
• Exactly one valid solution is guaranteed

Input:  numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]

Input:  numbers = [2, 3, 4], target = 6
Output: [1, 3]

Why This Problem Matters#

LeetCode 167 — Two Sum II — Input Array Is Sorted is the canonical entry point for the inward two-pointer technique, one of the most frequently tested patterns at FAANG. Amazon, Microsoft, Google, and Bloomberg use it as a 15-minute warm-up before harder variants like 3Sum or 4Sum. The constraint "O(1) extra space on a sorted array" is the real signal — it confirms the interviewer wants you to recognize when sorted order can replace a hash map.

The original Two Sum (LC 1) requires a hash map for O(n) time at O(n) space. The sorted guarantee here lets you achieve the same time with strictly less memory, which is why interviewers love it. If you can articulate the O(1)-space proof, you have demonstrated pattern recognition that generalizes to dozens of follow-ups.

In real-world systems, this pattern shows up whenever you need to find a target sum in a pre-sorted price list, a transaction ledger, or a sorted feature vector — common in ad-tech, fintech, and search ranking.

The Core Insight#

In a sorted array, place one pointer at the far left (l = 0) and one at the far right (r = n - 1). The pair (numbers[l], numbers[r]) is the sum of the smallest and largest current candidates. Compare against the target:

• If sum == target, return [l + 1, r + 1].
• If sum less than target, the left value is too small to ever pair with anything to the left of r, so advance l to a larger value.
• If sum greater than target, the right value is too large to pair with anything to the right of l, so move r to a smaller value.

Each step provably discards exactly one candidate that cannot be in any valid answer, so the loop runs in at most n minus 1 iterations. This "one move discards one non-answer" argument is the proof of correctness behind every inward two-pointer algorithm you will see in interviews.

Visual Dry Run#

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

Solution (Optimal)#

class Solution:
    def twoSum(self, numbers, target):
        l, r = 0, len(numbers) - 1
        while l < r:
            s = numbers[l] + numbers[r]
            if s == target:
                return [l + 1, r + 1]
            if s < target:
                l += 1
            else:
                r -= 1
        return []

var twoSum = function(numbers, target) {
    let l = 0, r = numbers.length - 1;
    while (l < r) {
        const s = numbers[l] + numbers[r];
        if (s === target) return [l + 1, r + 1];
        if (s < target) l++;
        else r--;
    }
    return [];
};

Time: O(n) — each pointer advances at most n steps before they cross. Space: O(1) — only two integer indices, no auxiliary structure.

Common Mistakes#

• Returning 0-indexed positions. The problem is 1-indexed, so always add 1.
• Reaching for a hash map. That violates the O(1) space requirement and signals you missed the sorted hint.
• Using l less than or equal to r instead of strict l less than r. When pointers meet, you would reuse a single index as both numbers.
• Binary searching for the complement. That is O(n log n) and strictly worse than the O(n) two-pointer pass.
• Starting l at 1 because the array is 1-indexed. Memory storage is always 0-indexed; only the answer is shifted.

Interview Tips#

• State out loud, "Because the array is sorted, I can use two pointers to avoid a hash map."
• Draw the array and label l and r on a whiteboard before coding.
• Explicitly mention the loop invariant: any valid pair must lie within the open window (l, r).
• Convert to 1-indexed at the very end, never inside the loop.
• Confirm with the interviewer whether duplicates exist — it changes follow-up handling.

Follow-up Questions#

• What if multiple valid pairs exist? Collect each match and advance both pointers, skipping duplicates.
• What if the array is unsorted? Either sort first for O(n log n) total or fall back to LC 1 with a hash map.
• How does this extend to 3Sum (LC 15)? Fix one element with an outer loop, run two pointers on the suffix.
• How would you adapt for floating-point tolerance? Compare abs(sum - target) less than epsilon instead of equality.
• What if the array is too large for memory and lives on disk? Use external sort plus a streaming two-pointer over sorted runs.

Key Takeaways#

• LeetCode 167 — Two Sum II — Input Array Is Sorted is solved in O(n) time and O(1) space using the inward two-pointer technique.
• The sorted invariant is what enables replacing a hash map with two indices.
• Each pointer move discards exactly one candidate that cannot be part of any answer.
• This pattern is the foundation for LC 15 (3Sum), LC 18 (4Sum), and LC 11 (Container With Most Water).
• Amazon, Microsoft, Google, and Bloomberg ask Two Sum II as a 15-minute screening warm-up.
• Always return 1-indexed positions and use a strict l less than r loop.
• The technique generalizes to any sorted sequence search where the relation is monotonic in both directions.