Pattern #06

Hashing

Essential

O(1) average lookup, frequency counting, grouping, and complement checks.

When to use

You need fast membership, counts, or grouping by a derived key. especially when a nested loop would be O(n²).

Recognition cues

Two sum / complement to target
Anagram / frequency equality
Group by signature (sorted string, count tuple)
First unique, duplicates, longest consecutive (set)

Common pitfalls

Using list instead of set/map (O(n) lookup)
Mutable keys or unstable signatures
Hash collisions are rare; logic bugs in key design are common

90-second recognition drill

Which pattern fits best?

Two sum / complement to target
Anagram / frequency equality
Group by signature (sorted string, count tuple)

GreedyHashingMonotonic StackLinked List Manipulation

Interactive

Mental model

A full worked walkthrough of the invariant. Pause, scrub the dots, or use ← →. Aim to narrate each step yourself.

Step 1 of 8

map{ }

target = 9

Two Sum in one pass: ask for the complement before inserting.

How to think about it

Trade space for time: store what you have seen (or need) under a key that makes the next check O(1).

Structure	Use
`Set`	membership, consecutive sequences
`Map value → index`	complement / two-sum
`Map key → count`	frequencies, anagrams
`Map key → list`	group anagrams / bucket

Complexity baseline

Average O(n) time, O(n) space. Worst-case hash behavior is rarely an interview focus; correct key design is.

Template

Same skeleton in TypeScript, Python, and C#. Adapt the invariant; keep the structure.

Hashing · Template

/** Hashing template: Two Sum with a value→index map. */
export function twoSum(nums: number[], target: number): number[] {
  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);
  }
  throw new Error("No solution");
}

/** Hashing template: Two Sum with a value→index map. */
export function twoSum(nums: number[], target: number): number[] {
  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);
  }
  throw new Error("No solution");
}

Path

Start path View in problem browser →

#ProblemTypeDifficultyDone

1#1 Two SumGuideeasy
2#49 Group AnagramsGuidemedium
3#128 Longest Consecutive SequenceGuidemedium
4#217 Contains DuplicateGuideeasy
5#242 Valid AnagramGuideeasy
6#347 Top K Frequent ElementsGuidemedium