Hash Map
Complement lookups and frequency counting solved; bidirectional mapping (Isomorphic Strings, Word Pattern) queued next.
The other pattern that comes up constantly enough to just keep in the toolkit alongside two pointers — trading O(n) space for turning an O(n²) lookup into O(1).
The sub-patterns
- A — Complement Lookup. Store
{value: index}and check for the complement before storing the current value. - B — Frequency Counting. One map of counts, decrement-and-check-zero to compare two collections.
- C — Bidirectional Mapping. Two maps enforcing a strict 1-to-1 relationship between two sequences.
The real trade-off worth remembering: two pointers on a sorted array costs an O(n log n) sort to save O(1) space; a hash map costs O(n) space to skip the sort entirely and run in O(n). Which one's better depends entirely on whether the input already happens to be sorted.
Complement Lookup
{value: index} map; check the complement before storing. Two Sum.
Frequency Counting
Single frequency map, decrement-and-check-zero pattern. Ransom Note, Valid Anagram.
Bidirectional Mapping
Two maps enforcing a strict 1-to-1 relationship between two sequences. Isomorphic Strings and Word Pattern queued — the character-mapping structure is understood conceptually, next up is an independent attempt.
Notes from readers
Comments — via GitHub