Two Sum II - sorted array, squeeze from both ends

Day 11 used a hash map because the array was unsorted. Today the input is sorted — converging two pointers find the pair in O(n) time and O(1) space. Same sum problem, different tool.

LeetCode #167: given a 1-indexed array of integers sorted in non-decreasing order, find two numbers that add up to target. Return their indices (1-based). Exactly one solution exists; you may not use the same element twice.

The problem

twoSum([2, 7, 11, 15], 9)  → [1, 2]   // 2 + 7
twoSum([2, 3, 4], 6)       → [1, 3]   // 2 + 4
twoSum([-1, 0], -1)        → [1, 2]   // -1 + 0

Day 11’s hash map still works here. But sorted order is free information. If you ignore it, you pay O(n) extra space for a map you didn’t need.

Approach 1: Brute force (with early break)

function twoSumBrute(numbers, target) {
  const n = numbers.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const sum = numbers[i] + numbers[j];
      if (sum === target) return [i + 1, j + 1];
      if (sum > target) break; // sorted: rest of row only gets larger
    }
  }
  return null;
}

Correct. Early break uses sortedness a little. Still O(n²) when the pair sits late. At n=10K in our lab: 54,204 μs median.

Approach 2: Binary search for the complement

function twoSumBinary(numbers, target) {
  const n = numbers.length;
  for (let i = 0; i < n; i++) {
    const need = target - numbers[i];
    let lo = i + 1, hi = n - 1;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (numbers[mid] === need) return [i + 1, mid + 1];
      if (numbers[mid] < need) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return null;
}

O(n log n) time, O(1) space. Respects sorted order. Good interview middle step — but you can do better without the log factor.

Approach 3: Converging two pointers (the pattern)

function twoSum(numbers, target) {
  let l = 0, r = numbers.length - 1;
  while (l < r) {
    const sum = numbers[l] + numbers[r];
    if (sum === target) return [l + 1, r + 1]; // 1-indexed
    if (sum < target) l++;  // need bigger sum → move left rightward
    else r--;               // need smaller sum → move right leftward
  }
  return null; // problem guarantees a pair
}

Why this is safe on a sorted array:

• If sum < target, every pair using numbers[l] with something left of r is even smaller — so discard l.
• If sum > target, every pair using numbers[r] with something right of l is even larger — so discard r.
• Each step removes one index forever. At most n−1 steps. O(n) time, O(1) space.

Day 11 vs Day 40 — pick the tool

Input	Best tool	Time	Extra space
Unsorted (LeetCode #1)	Hash map complement (Day 11)	O(n)	O(n)
Already sorted (#167)	Two pointers (today)	O(n)	O(1)
Unsorted, need original indices, space tight	Sort + two-ptr needs index pairs stored	O(n log n)	O(n) for index pairs

Interview trap: applying two-pointer values on an unsorted array without sorting first. The squeeze proof requires order. Hash does not.

Worked walk — multi-step squeeze

numbers = [1, 2, 4, 6, 10], target = 8
L=1, R=10 → sum 11 > 8 → R--
L=1, R=6  → sum 7  < 8 → L++
L=2, R=6  → sum 8  = 8 → return indices of 2 and 6

Three steps, three discards. No map, no binary search tree in your head — just “too small / too big / done.” That is the interview voice you want.

Benchmark — honest walk (Node, 30-run median)

Array 1..n, target (n-1)+n — the unique pair is the last two elements, so two pointers must walk almost the full length (not a one-step end-pair cheat). The benchmark script and standalone write-up are not included in this repository.

Approach	n=1K (μs)	n=10K (μs)	n=100K (μs)
Brute (early-break)	527.1	54,203.9	skip
Binary search / i	33.9	160.1	2,126.9
Hash map (Day 11 style)	78.4	806.0	9,721.4
Two pointers	4.5	17.4	163.6

Headlines (n=100K): two-ptr is 13.0× faster than binary-per-i and 59.4× faster than hash map — plus O(1) space. At n=10K vs early-break brute: ~3,100×.

Why is hash so slow here? Map allocates and hashes every key while two-ptr only reads two integers per step. Sorted order already encodes the structure the map would rediscover.

Space honesty

Hash map is O(n) extra. Two pointers is O(1) extra (ignoring the input array itself). In interview talk: “I use the sorted property to discard one end each step, so I never need a set of seen values.” That sentence is the pattern.

What breaks? — Anti-patterns

1. Using Day 11 hash “because Two Sum.” Works, wastes space and constants when sorted is given. Fix: if sorted → squeeze; if not → hash (or sort first).

2. Returning 0-based indices. LeetCode #167 is 1-indexed. Off-by-one fails every case. Fix: return [l + 1, r + 1].

3. Moving the wrong pointer. sum < target but you decrement r → sum only gets smaller. Fix: too small → L++; too big → R—.

4. Two-ptr on unsorted values without sorting. The discard argument is false; you can miss the pair. Fix: sort first (track original indices if required) or use hash.

How it connects

• Day 11 (Two Sum): same question, unsorted input → hash complement. Today the free sort flips the best tool.
• Day 39 (Valid Palindrome): same converging geometry (L and R walk toward each other). Palindrome compares equality; Two Sum II compares sum vs target.
• Day 33 (Is Subsequence): two pointers, same-direction family — different geometry, same “two indices tell a story” idea.

Transfer questions

1. If the array were unsorted and you sorted it first, what do you lose if the problem needs original indices?
2. Why is binary-search-per-i O(n log n) but still often slower than two pointers’ O(n) in practice?
3. How would you adapt the squeeze for “3Sum” (find three numbers that sum to 0)?

Quiz

Your teach step

Close this lesson. Write the “Explain like I’m 10” and the “60-second LinkedIn version” from memory. Focus on: sorted → squeeze; too small L++; too big R—; Day 11 hash vs Day 40 O(1) space; the 13.0× / 59.4× benches. Post it, and paste the link.

Questions? Ask the agent — 3Sum setup, Container With Most Water, or Two Sum (unsorted) recap.