Hashing

Trade memory for time: a hash map gives you average O(1) lookup, so membership and counting questions collapse from O(n²) to O(n).

Key ideas

  • —A hash set answers "have I seen this?" in O(1) on average.
  • —A hash map of value → index lets you find complements in one pass.
  • —Group by a canonical key (sorted string, signature) to bucket related items.

The complement trick

Many "find a pair that sums to k" problems become one pass: for each value x, check whether k − x is already in the map before inserting x. You never need a second loop because the map remembers everything you have seen so far. This is why Two Sum is O(n) rather than O(n²).

Canonical keys and counting

When you need to detect anagrams or duplicates, reduce each item to a canonical form — a sorted string or a character-frequency tuple — and use it as a map key. Items that share a key belong together. Frequency maps also power problems like Longest Consecutive Sequence, where membership tests replace sorting.

Practice this

Sources

← All lessonsNext: Binary Search →