Chapter 10 — Hash Tables & Sets
Source:
src/main/kotlin/hashtable/andsrc/main/kotlin/array/hashtable/Master idea: a hash table trades ordering for speed — it answers “is this key present?” and “what value is stored under this key?” in amortized $O(1)$, at the price of losing sorted order. Nearly every problem in this chapter is one of three moves: complement lookup, value-to-state maps, or membership + canonicalization.
Prerequisites: arrays, and the frequency/grouping ideas from Chapter 9 — many string problems are hash-table problems wearing characters.
Problems at a glance (this chapter’s core set)
| # | Problem | Pattern | Complexity | Page |
|---|---|---|---|---|
| 10.1 | Two Sum | complement lookup | $O(n)$ | → |
| 10.2 | Contains Duplicate II | value -> last index | $O(n)$ | → |
| 10.3 | Longest Consecutive Sequence | set + run-start detection | $O(n)$ | → |
| 10.4 | Valid Sudoku | per-row/col/box sets | $O(81)$ | → |
| 10.5 | First Unique Character | frequency map | $O(n)$ | → |
| 10.6 | Design HashMap | open addressing | $O(1)$ amortized | → |
| 10.7 | Roman To Integer | right-to-left accumulation | $O(n)$ | → |
| 10.8 | Subarray Sum Equals K | prefix sums + frequency map | $O(n)$ | → | | 10.9 | Count Rectangles Formed By Points | diagonal pairing + set lookup | $O(n^2)$ | → | | 10.10 | First Missing Positive | index-as-memo marking | $O(n)$ | → | | 10.11 | Subarray Sums Divisible By K | remainder map (floorMod) | $O(n)$ | → | | 10.12 | Rank Transform Of An Array | sort + first-occurrence map | $O(n log n)$ | → | | 10.13 | Unique Number Of Occurrences | frequency map + set-size | $O(n)$ | → | | 10.14 | Integer To English Words | 1000-block tables + dfs | $O(1)$ | → | | 10.15 | Max Points On A Line | slope frequency map | $O(n^2)$ | → | | 10.16 | Design HashMap | open addressing | $O(1)$ | → | | 10.17 | Group Shifted Strings | gap-sequence keys | $O(nL)$ | → | | 10.18 | Equal Row And Column Pairs | sequence-vector keys | $O(n^2)$ | → | | 10.19 | Determine If Two Strings Are Close | char-set + freq-multiset | $O(n)$ | → | | 10.20 | Unique Length-3 Palindromes | first/last + middle sets | $O(n)$ | → | | 10.21 | Max Number Of K-Sum Pairs | complement count map | $O(n)$ | → | | 10.22 | Find Winner TicTacToe | line-check per move | $O(1)$ | → | | 10.24 | Contiguous Array | prefix-sum first-occurrence | $O(n)$ | → | | 10.25 | Set Mismatch | sum-arithmetic | $O(n)$ | → | | 10.26 | Detect Squares | diagonal completion | $O(n)$ | → | | 10.27 | Snapshot Array | per-index history logs | $O(log C)$ | → | | 10.28 | Find Unique Binary String | Cantor diagonal | $O(n)$ | → | | 10.29 | Intersection Of Two Arrays | set intersection | $O(n+m)$ | → | | 10.30 | First Letter To Appear Twice | bitmask detect | $O(n)$ | → | | 10.31 | Design Number Container System | dual maps | $O(log n)$ | → | | 10.32 | Design File System | path map | $O(L)$ | → |
The rest of the hashtable/ directories
src/main/kotlin/hashtable/ adds: Integer To Roman, H-Index, Intersection Of Two Arrays, Maximum Frequency Stack, Design A Number Container System, Design File System, Count Number Of Bad Pairs, Word Break variants. src/main/kotlin/array/hashtable/ adds: First Missing Positive, Degree Of An Array, Valid Sudoku variants, Set Mismatch, Rank Transform Of An Array, Unique Number Of Occurrences, Integer To English Words, Equal Row And Column Pairs, and more. The LRU/LFU cache designs live in src/main/kotlin/cache/ and are the “map + structure” capstone of this chapter’s design problems.
New pages are appended to the table above as they’re written.