The Two-Sum Pattern

Two-sum is the most-asked interview question in the industry, not because it's clever but because it's the cleanest possible demonstration of "a hash map turns an O(n²) search into an O(n) one" — the exact idea the last two lessons built up to. It's worth working through properly once, because the pattern behind it (look for a complement, not a match) reappears constantly.

The problem

Given an array of numbers and a target, find two numbers that add up to the target — return their values (or indices).

twoSum([2, 7, 11, 15], 9); // 2 + 7 === 9 → [2, 7]

Brute force: check every pair

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

This is the same shape as closestPair from the time-complexity lesson — nested loops checking every pair — and by that lesson's counting argument, it's O(n²).

The hash-map version: look for the complement

The insight: for each number x in the array, you're not looking for another specific number — you're looking for whatever number would complete the sum, target - x. That's the complement. Instead of scanning the rest of the array for it, ask a hash map "have I already seen this complement?" — O(1) average, instead of an O(n) inner scan.

function twoSum(arr, target) {
  const seen = new Map(); // value -> index, or just a Set if you only need the values
 
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    if (seen.has(complement)) {
      return [complement, arr[i]];
    }
    seen.set(arr[i], i); // only add AFTER checking, so an element never pairs with itself
  }
 
  return null;
}

Trace it on [2, 7, 11, 15], target 9:

• i=0, arr[i]=2. Complement is 7. seen is empty — no match. Add 2 to seen.
• i=1, arr[i]=7. Complement is 2. seen has 2 — match! Return [2, 7].

Only one pass, and the answer came back before even reaching the array's end. The order of operations matters: checking for the complement before adding the current element means an element is never matched against itself, and any match found is guaranteed to pair the current element with an earlier one — you'll never report the same index twice.

This drops the complexity from O(n²) to O(n) time, at the cost of O(n) auxiliary space for the map — the classic time-for-space trade this whole part of the course has been building toward.

A real frontend framing

A cart page needs to find two line items whose prices sum exactly to a $50 gift-card balance, so it can suggest "add these two items to use up your card exactly." If this recalculates on every add-to-cart click across a 40-item cart, the brute-force version does 1,600 comparisons per click — invisible once, but it's the "cheap thing called repeatedly" pattern this course opened with, and it compounds across a session. The hash-map version does 40 lookups per click, and the difference becomes real the moment the cart (or the click frequency) grows past a trivial size.

function findGiftCardPair(items, targetTotal) {
  const seen = new Map(); // price -> item
 
  for (const item of items) {
    const complementPrice = targetTotal - item.price;
    if (seen.has(complementPrice)) {
      return [seen.get(complementPrice), item];
    }
    seen.set(item.price, item);
  }
 
  return null;
}

What to remember

• Two-sum's brute-force solution is O(n²) — check every pair. The hash-map version is O(n) — for each element, ask a map for its complement instead of scanning for it.
• "Look for the complement, not a direct match" is the generalizable idea: it's the same "ask a hash map instead of scanning" trick as the last two lessons, applied to a relationship between two values instead of one value's presence or count.
• Checking for the complement before inserting the current element avoids matching an element with itself and guarantees any match pairs with an earlier element.
• The O(n) time trade costs O(n) auxiliary space for the map — worth it the moment the operation runs more than trivially often or over more than a trivial amount of data.