Pattern 1 of 18 · Foundations

Arrays & Hashing

The foundation. Master hash maps and sets to trade space for time and turn O(n²) brute force into O(n).

Arrays give O(1) index access; hash maps and sets give O(1) average lookup, insert, and delete by trading space for speed. Together they're the toolkit for turning brute-force O(n²) comparisons into a single O(n) pass.

Key concepts

  • Hash map: key → value lookup in O(1) average time — use it to remember "have I seen this before?" or to count occurrences.
  • Hash set: like a hash map but only tracks membership, not values.
  • Frequency counting: tally occurrences of each element in one pass.
  • Prefix/suffix products or sums: precompute running totals so you never recompute a range from scratch.

When to use it

  • You need to check "have I seen this value before?" quickly.
  • You're counting occurrences or grouping items by a derived key (e.g. sorted letters for anagrams).
  • A nested loop is comparing every pair — a hash map can often replace the inner loop.

Tips

  • Reach for a hash map before reaching for nested loops — most "find the pair/duplicate" problems collapse to O(n) with one.
  • For anagram-style grouping, a sorted string or character-count tuple makes a reliable hash key.
  • Watch for integer overflow when precomputing products across large arrays.

Practice problems (9)

Blind 75 (8):

More from Blind 150 (1):

Two Pointers →

See the full roadmap →