4.5.2 — Two Sum II: Input Array Is Sorted

LeetCode 167 · Medium

The problem

The array is sorted. Find the two numbers adding to target and return their positions, 1-indexed. Exactly one answer exists, and you must use O(1) extra space.

numbers = [2, 7, 11, 15], target = 9   →  [1, 2]
numbers = [2, 3, 4],      target = 6   →  [1, 3]

Constraints:

• The array length can be up to 30,000.
• Values can be negative, and the target can be negative.
• The array is sorted in non-decreasing order.
• The tests guarantee exactly one solution exists, so we don't have to worry about finding zero or multiple pairs.

Plain English: You have a list of numbers sorted from smallest to largest. You need to find two numbers that add up perfectly to a specific target number. When you find them, hand back their positions (counting from 1, not the usual 0). You aren't allowed to use extra memory like a hash map.

Two details decide the solution. The array is sorted, which is the gift. And the space must be O(1), which rules out the hash map from 4.4.3.

The naive approach

The brute-force way would be to pair every single number with every other number. For the first number, check the rest. For the second number, check the rest.

Why it fails: If there are 30,000 numbers, checking every pair takes 30,000 \times 30,000 \approx 900 million operations. That's an O(n^2) time complexity, which will result in a Time Limit Exceeded (TLE) error. The brute force wastes time by completely ignoring the fact that the array is already sorted.

The pattern

Put one pointer on the smallest value and one on the largest. Add them.

• Sum too small? The only way to grow it is to move the left pointer right, because everything to the right is larger.
• Sum too big? Move the right pointer left.
• Equal? Done.

Each step throws away a whole set of possibilities without checking them one by one.

The ELI5 Analogy: Imagine you and a friend are looking for a perfectly balanced see-saw. You start with the lightest kid on the far left and the heaviest kid on the far right. If the see-saw is too heavy on the right, you need a lighter kid on the right, so the right person steps inward. If the see-saw is too light, you need a heavier kid on the left, so the left person steps inward. Because the kids are perfectly lined up by weight, you know exactly which direction to move. The "aha moment" is realizing that you never have to blindly guess; the sum itself tells you exactly which pointer is wrong.

Why discarding is safe

This is the part worth understanding, because the same argument justifies every two-pointer solution in this chapter.

Suppose numbers[l] + numbers[r] < target. Ask what numbers[l] could still pair with. Its largest possible partner is numbers[r], since the array is sorted and r is the far end. If even that partner is too small, then numbers[l] cannot reach the target with anything. It is finished. Move past it.

The mirror argument covers the too-big case. So each move eliminates one element permanently, and no move ever needs to be undone.

That shape — this element cannot be part of any answer, so discarding it is safe — is the proof behind two pointers everywhere. If you cannot make that argument for a problem, two pointers is the wrong tool.

The solution

Python

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            total = numbers[l] + numbers[r]
            if total == target:
                return [l + 1, r + 1]     # the problem is 1-indexed
            if total < target:
                l += 1
            else:
                r -= 1
        return []

TypeScript

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

The + 1 on the return is the only thing here that trips people up. The problem indexes from 1.

Code Walkthrough

• l, r = 0, len(numbers) - 1: We place our left pointer at the start (smallest number) and right pointer at the end (largest number). If you started them anywhere else, you wouldn't know which way to safely move them.
• while l < r:: The pointers move towards each other. They must not cross or land on the same index, because you need exactly two distinct numbers to form a pair.
• if total == target:: We found our match. We return [l + 1, r + 1] immediately to satisfy the 1-indexed requirement.
• if total < target:: The sum is too small. Since numbers[r] is already the largest available partner for numbers[l], there is no way numbers[l] can be part of the solution. We abandon numbers[l] by doing l += 1.
• else: (which means total > target): The sum is too big. Even the smallest available partner (numbers[l]) makes the sum too big for numbers[r]. We abandon numbers[r] by doing r -= 1.

Trace

Let's trace numbers = [2, 7, 11, 15], target = 9:

Step	l (val)	r (val)	Sum	Condition	Action
1	0 (2)	3 (15)	17	17 > 9	Too big, move r left (r -= 1)
2	0 (2)	2 (11)	13	13 > 9	Too big, move r left (r -= 1)
3	0 (2)	1 (7)	9	9 == 9	Match! Return [1, 2]

Complexity

O(n) time and O(1) space. The two pointers together cover the array once, since each step moves exactly one of them and they never move apart.

Compare with binary search, which would be O(n \log n): for each element, binary search for its partner. Two pointers is strictly better because it reuses the work from the previous comparison instead of starting a fresh search each time.

Let's derive these directly from the code:

• Time Complexity: O(n). We have two pointers, l and r. Every time the while loop runs, either l increases by 1 or r decreases by 1. They start n elements apart and stop when they meet. In the absolute worst-case scenario, they will take exactly n-1 steps combined. The work done inside the loop (addition, comparison) takes O(1) constant time. Therefore, (n-1) \times O(1) = O(n) total time.
• Space Complexity: O(1). We are only storing three integer variables (l, r, and total). We don't build any new arrays or use a hash map, so memory usage remains constant regardless of how huge the input array gets.

Edge Cases

• Negative numbers: The algorithm works perfectly with negatives (e.g., [-5, -2, 3], target -2). The logic of "move right to get smaller, move left to get bigger" holds true strictly because the array is mathematically sorted.
• Duplicates: What if the array is [3, 3, 4], target 6? The pointers will naturally land on the two 3s. The problem guarantees exactly one valid answer, so we don't have to handle multiple pairs of duplicates.

Two pointers or a hash map?

the input is	you must return	use
sorted	anything	two pointers, O(1) space
unsorted	indices into the original array	hash map
unsorted	values only, memory tight	sort first, then two pointers

Sorting an unsorted array to use two pointers destroys the original indices, which is exactly why 4.4.3 cannot use this method.

Where this goes next

This is the engine inside larger problems. Fix one element and run this on the rest, and you have 3Sum. Fix two and you have 4Sum. That is 4.5.3.

Next: 4.5.3 3Sum — this loop wrapped in another loop, where all the real difficulty turns out to be duplicate handling.

What the interviewer will push on

"Why can't we use a hash map here like we did in normal Two Sum?" You can, but it would take O(n) extra space. By taking advantage of the fact that the array is already sorted, we can drop the space complexity down to O(1) using two pointers.

"What if there were multiple valid pairs? How would you return all of them?" You would keep the same two-pointer logic, but instead of returning immediately when total == target, you would add the pair to a result list, and then move both l and r inward. You'd also need to add while loops to skip past identical adjacent numbers to avoid adding duplicate pairs to your result.