HARD Lab · Arrays & Hashing · 01

1. Two Sum

Find the two indices whose values add up to a target. The brute force checks every pair in O(n²); the elegant answer makes a single pass, using a hash map as memoryso each element can instantly ask "have I already seen my missing half?"

● EasyHash MapComplement TrickTypeScript

PROBLEM What we're solving

Given nums = [2,7,11,15] and target = 9, return the indices of the two numbers that sum to the target. Here nums[0] + nums[1] = 2 + 7 = 9, so the answer is [0, 1]. Exactly one valid pair is guaranteed, and you can't reuse the same index twice.

KEY IDEA Remember what you've seen

The complement trick → for the current value x, the only partner that works is target − x. Instead of scanning the rest of the array for it, keep a hash map of every value seen so far → its index and check that partner in O(1).

That converts "search for the partner" (O(n) each, O(n²) total) into "look it up" (O(1) each, O(n) total). The map turns the array into instant memory.

RECIPE One pass, two moves per element

  • 1 · Compute the complement. need = target − nums[i].
  • 2 · Look it up. If needis already a key in the map, you've found the pair: return [map.get(need), i].
  • 3 · Otherwise store yourself. Put nums[i] → i into the map and move on.
Classic confusion → store after you check, not before. If you store first, an element could match itself (e.g. target 6 with a single 3 would falsely pair index i with itself). Check the map for the complement first, then insert.

COST Complexity & alternatives

Brute force
O(n²)
Every pair (i, j). Simple but slow.
Hash map, one pass
O(n)
O(n) time, O(n) space for the map.

What about sorting + two pointers?

Sorting then walking two pointers inward is O(n log n) and O(1) extra space — but sorting scrambles the original indices, and this problem wants indices. You'd have to store (value, index) pairs and sort those. The hash map is cleaner here. (Two pointers shines on the sorted variant and on 3Sum.)

Pattern transfer → the "store seen values in a hash map / set" move powers Contains Duplicate, Longest Consecutive Sequence, Subarray Sum Equals K, and the two-pointer cousin 3Sum.

RUN IT Watch the map fill

step 0 / 4
STARTStart with an empty map. Scan left to right; each value looks up its complement target − value.
2
0
7
1
11
2
15
3
Hash map (value → index)
empty
Status
empty
current istored in mapmatched pair
slowfast

TYPESCRIPT The solution, annotated

twoSum.ts
function twoSum(nums: number[], target: number): number[] {
  // value -> the index where we last saw it
  const seen = new Map<number, number>();

  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];   // the complement
    if (seen.has(need)) {
      return [seen.get(need)!, i];   // found the pair
    }
    seen.set(nums[i], i);          // remember for later
  }
  return [];                       // problem guarantees we never reach here
}

Reading it block by block

Line 3 — the memory. A Map from value to index. We use a Map (not a plain object) so numeric keys stay numeric and lookups are clean O(1).
Line 6 — the complement. For each value, the only useful partner is target − nums[i]. We compute it once.
Lines 7–9 — check before store. If the complement is already in the map, its stored index plus the current i is the answer. Checking first guarantees the two indices are distinct.
Line 10 — record yourself. Only after the check do we store the current value, so future elements can find us as their complement.
Complexity → one pass over n elements, and every map operation (has/get/set) is amortized O(1). Total O(n) time, O(n) space for the map.

INTERVIEWFollow-ups they'll ask

  • "What if the array is already sorted?" Use two pointers from both ends moving inward — O(n) time, O(1) space, no map needed.
  • "Return all pairs, not just one."Don't early-return; keep scanning and collect every match (watch for duplicates).
  • "What if no solution exists?" Return [] or a sentinel. The classic version guarantees exactly one.
  • "Can the same element be used twice?" No — checking the map before inserting is what prevents pairing an index with itself.

MNEMONIC The one-liner

"Ask the map for my missing half — then leave my own number behind."

TRIGGERS When you see ___ → reach for ___

"find two that sum to target"hash map of complements
"have I seen X before?" in one passMap / Set as memory
array is sorted + return valuestwo pointers inward
need original indicesstore value → index

SKELETON The reusable shape

skeleton.ts
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
  const need = target - nums[i];
  if (seen.has(need)) return [seen.get(need)!, i];
  seen.set(nums[i], i);   // check THEN store
}

FLASHCARDS Tap to flip

What is the "complement" of nums[i]?
target − nums[i] — the only value that can pair with it.
tap to flip
1 / 6
Answer to reveal explanations. No penalty for retries.Score: 0 / 6
QUESTION 01
What is the optimal time complexity of Two Sum?
QUESTION 02
For value nums[i], which value does the map look up?
QUESTION 03
Why do we check the map before inserting the current value?
QUESTION 04
The hash map stores which mapping?
QUESTION 05
For nums=[3,2,4], target=6, the answer is:
QUESTION 06
If the input were guaranteed sorted and you could return values, the best approach is: