Two Sum — hash map complement lookup

The problem

LeetCode 1 — Two Sum. Given an array of integers and a target, return the indices of the two numbers that add up to the target.

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]  (because nums[0] + nums[1] = 2 + 7 = 9)

You can assume each input has exactly one solution, and you can’t use the same element twice.

The brute force: check every pair

The obvious approach: compare every pair of numbers. For each nums[i], check every nums[j] after it. If they sum to target, return both indices.

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

Time: O(n²) — for 10,000 elements, that’s up to 50 million comparisons. Space: O(1) — no extra data structures.

This works. But it’s slow. At n=10,000, the brute force takes 37ms. We can do better.

The key insight: the complement

Here’s the realization that changes everything:

For each number x, the number you need is target - x. That’s the complement.

If target = 9 and you see 2, you need 7. You don’t need to scan the array for 7 — you just need to remember: “have I seen 7 before?”

This is the same pattern from Day 4 (hash set: “have I seen this?”) — but instead of storing the value, we store the index (because the problem asks for indices, not values).

Approach 2: two-pass hash map

Build the hash map first, then scan for complements.

function twoSum(nums, target) {
  const map = {};
  // Pass 1: build the map
  for (let i = 0; i < nums.length; i++) {
    map[nums[i]] = i;
  }
  // Pass 2: find the complement
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map[complement] !== undefined && map[complement] !== i) {
      return [i, map[complement]];
    }
  }
}

Time: O(n) — two passes, each O(n). Space: O(n) — the hash map stores every element.

Approach 3: one-pass hash map

Why build the entire map first? As you walk through the array, check if the complement already exists in the map. If it does, you’re done. If not, add the current number to the map.

function twoSum(nums, target) {
  const map = {};
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map[complement] !== undefined) {
      return [map[complement], i];
    }
    map[nums[i]] = i;
  }
}

Time: O(n) — one pass. Space: O(n) — worst case, the map stores every element before finding the pair.

The one-pass is subtly better: it can return early (before processing the whole array) if the pair appears early. And it never stores more entries than necessary.

The benchmark

Real timing, 30 runs per size, median reported. JavaScript (Node.js 24), warm starts.

Size	Brute Force	Two-Pass Hash	One-Pass Hash	Speedup
1,000	0.41ms	0.080ms	0.058ms	7×
5,000	7.98ms	0.548ms	0.243ms	33×
10,000	37.34ms	1.177ms	0.652ms	57×
50,000	—	9.503ms	3.282ms	—
100,000	—	18.437ms	18.821ms	—

Key findings:

1. Brute force scales as O(n²) — at n=10,000 it’s already 37ms vs 0.65ms. At n=50,000 it would take ~1.5 seconds (skipped to save time).
2. One-pass beats two-pass at small n — fewer map insertions, early exit possible.
3. At n=100,000, they converge — hash map resize overhead dominates, and the one-pass loses its early-exit advantage (the pair is at the end by construction).

Same Big O. Different constant. Different real-world speed.

The hash pattern trilogy

Three days, three hash-based problems, three different questions:

Day	Problem	Question	Structure
4	Contains Duplicate	”Have I seen this?”	Hash set
5	Valid Anagram	”How many of each?”	Hash map (count)
11	Two Sum	”Have I seen my complement?”	Hash map (index)

The pattern: when the question is about membership or counting, a hash gives you O(1) lookup. The trick is knowing what to store — the value (Day 4), the count (Day 5), or the index (Day 11).

Check your understanding