Two Sum II: why sorted order makes two pointers work

The original Two Sum gave you an unsorted array and let you use a hash map. This one takes that convenience away and replaces it with something more valuable: a guarantee. The array is sorted. That single fact changes the entire structure of the solution.

What the problem actually gives you

numbers is 1-indexed, sorted in non-decreasing order, and exactly one pair of indices sums to target. The constraints: up to 30,000 elements, values and target all in [-1000, 1000], and — most importantly — you must use constant extra space. That last constraint rules out the hash map approach from the start.

Two constraints together point you at one answer. The question is not "how do I find a pair?" It is "how do I exploit sorted order to find a pair in linear time?"

Brute force: O(n²)

The naive approach is two nested loops — try every pair, return when the sum matches.

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        n = len(numbers)
        for i in range(n - 1):
            for j in range(i + 1, n):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]
        return []

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int n = numbers.Length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (numbers[i] + numbers[j] == target)
                    return new int[] { i + 1, j + 1 };
            }
        }
        return new int[0];
    }
}

O(n²) time, O(1) space. Satisfies the space constraint but ignores sorted order entirely. On a 30,000-element array you're looking at up to 450 million comparisons. It passes LeetCode's judge today because the constraints are small enough — but it is the wrong lesson. The point of this problem is to understand why sorting unlocks something better.

Walk through example 1: numbers = [2, 7, 11, 15], target = 9.

• i=0, j=1: 2 + 7 = 9. Match. Return [1, 2].

Done on the first pair. Lucky. On a worst-case input, the matching pair is near the end and you've visited almost every combination before landing on it.

Binary search: O(n log n)

Sorting lets you do something smarter. Fix the left element, binary-search for its complement target - numbers[i] in the remaining suffix.

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        def binary_search(start: int, val: int) -> int:
            lo, hi = start, len(numbers) - 1
            while lo <= hi:
                mid = (lo + hi) // 2
                if numbers[mid] == val:
                    return mid
                elif numbers[mid] < val:
                    lo = mid + 1
                else:
                    hi = mid - 1
            return -1
 
        for i in range(len(numbers) - 1):
            complement = target - numbers[i]
            j = binary_search(i + 1, complement)
            if j != -1:
                return [i + 1, j + 1]
        return []

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int BinarySearch(int start, int val) {
            int lo = start, hi = numbers.Length - 1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (numbers[mid] == val) return mid;
                else if (numbers[mid] < val) lo = mid + 1;
                else hi = mid - 1;
            }
            return -1;
        }
 
        for (int i = 0; i < numbers.Length - 1; i++) {
            int complement = target - numbers[i];
            int j = BinarySearch(i + 1, complement);
            if (j != -1)
                return new int[] { i + 1, j + 1 };
        }
        return new int[0];
    }
}

Walk through example 2: numbers = [2, 3, 4], target = 6.

• i=0: complement = 6 - 2 = 4. Binary search in [3, 4] starting at index 1. mid=1, 3 < 4, move lo to 2. mid=2, 4 == 4. Found at index 2. Return [1, 3].

O(n log n) time, O(1) space. Better than brute force, but there's a structural waste: the binary search for i=0 explored a lot of the right half. The search for i=1 ignores all that and starts over. You're paying for knowledge you immediately discard.

Two pointers: O(n)

Place one pointer at index 0 (left), one at index n-1 (right). Compute numbers[left] + numbers[right]. If it equals target, return immediately. If the sum is less than target, you need a larger value — right is already at its ceiling within the current window, so move left forward. If the sum exceeds target, you need a smaller value — left is at its floor, so pull right back.

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            current = numbers[left] + numbers[right]
            if current == target:
                return [left + 1, right + 1]
            elif current < target:
                left += 1
            else:
                right -= 1
        return []

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int left = 0, right = numbers.Length - 1;
        while (left < right) {
            int current = numbers[left] + numbers[right];
            if (current == target)
                return new int[] { left + 1, right + 1 };
            else if (current < target)
                left++;
            else
                right--;
        }
        return new int[0];
    }
}

Walk through example 1: numbers = [2, 7, 11, 15], target = 9.

left=0, right=3: 2 + 15 = 17 > 9  -> move right left
left=0, right=2: 2 + 11 = 13 > 9  -> move right left
left=0, right=1: 2 +  7 =  9 == 9 -> return [1, 2]

Walk through example 3: numbers = [-1, 0], target = -1.

left=0, right=1: -1 + 0 = -1 == -1 -> return [1, 2]

Two pointers terminates immediately when the array has only two elements — which is the minimum size the constraints allow.

The pointer convergence for example 1, step by step:

O(n) time, O(1) space. Each step moves at least one pointer. The pointers converge. Every element is visited at most once.

Why each move is safe, not just fast

The correctness argument is worth understanding carefully, because it's the same argument that makes two pointers work on many other problems.

The decision at each step is mechanical, but why each branch is safe is not:

At any point in the loop, the answer must have left_answer >= left and right_answer <= right. The pointers always bracket the solution.

When we move left because the sum is too small: we are not just moving a pointer, we are eliminating every pair (left, j) for all j in [left+1, right] simultaneously. Why? Because numbers[left] + numbers[j] <= numbers[left] + numbers[right] < target for every such j. The current numbers[left] cannot pair with anything in the remaining window to reach target. Discarding it loses nothing.

When we move right because the sum is too large: numbers[i] + numbers[right] >= numbers[left] + numbers[right] > target for every i in [left, right-1]. The current numbers[right] is too large for any remaining partner. Discarding it is safe.

This is not guessing. Each move is elimination — and elimination is only safe because the array is sorted. Remove the sorted guarantee, and both steps break. Which is exactly why you cannot apply this trick to the original Two Sum without sorting it first (and if you sort it, you need to track original indices separately).

Comparing the approaches

The binary search approach has its place: in problems where you need to search within a fixed prefix or suffix, or when the two-pointer elimination argument does not apply. But for this specific structure — find a pair, sorted array, constant space — two pointers is the canonical answer.

Edge cases worth knowing

Two-element array. With only two elements, left=0 and right=1 on the first iteration. The problem guarantees exactly one solution, so this returns immediately. No special handling needed.

Negative numbers. The constraints allow values down to -1000 and target down to -1000. Two pointers handles this naturally — the movement logic depends only on whether the current sum is above or below target, not on sign.

Answer at the extremes. If numbers[0] + numbers[n-1] == target, the answer is found on the very first iteration. If the answer is somewhere in the middle, the pointers will converge to it. The correctness argument holds either way.

Duplicate values. The problem does not say values are unique, only that there's exactly one valid pair of indices. Two pointers handles duplicates without modification — if numbers[left] equals numbers[left+1], moving left skips to the duplicate and the algorithm continues normally.

What triggers this pattern

A few keywords that should immediately bring two pointers to mind:

• "sorted array" + "find a pair" + any sum/difference condition
• "constant extra space" (rules out hash maps)
• "1-indexed return" (just cosmetic — add 1 to each pointer before returning)
• Any problem where brute force is O(n²) and you're asked to improve it, given sorted input

The broader pattern: any time you can formulate "current sum too large -> shrink one side; too small -> grow the other side" with sorted data, two pointers reduces O(n²) to O(n).

What the space constraint is telling you

The problem says "your solution must use only constant extra space." Read that as: no hash map. A hash map would give you O(n) time but O(n) space. Two pointers gives you O(n) time and O(1) space. The constraint is not a punishment — it is a hint that the sorted order is doing the heavy lifting and you should use it directly.

In an interview, I would write the two-pointer version and explain the correctness argument without being asked. Not to show off — but to demonstrate the difference between using a technique and understanding it. "Move left when the sum is too small" is a rule. "Moving left eliminates all remaining pairs for this index, because sorted order guarantees they all undershoot target too" is a reason. Interviewers hear the first answer all the time. They remember the second one.

Related problems

• LeetCode 1 — Two Sum: same family, unsorted array, hash map instead of two pointers. Start here if you haven't.
• LeetCode 15 — 3Sum: extends to three elements. The outer loop fixes one number and runs two pointers over the rest. Sorted order is still the key.
• LeetCode 18 — 4Sum: extends further to four elements. Same structure, two more nested loops.
• LeetCode 11 — Container With Most Water: two pointers from both ends, move the shorter bar inward. Same elimination logic, different objective.
• LeetCode 125 — Valid Palindrome: two pointers walking toward each other, checking characters instead of sums. The movement rule is different; the converging pattern is the same.