Hash Tables
Hash tables give O(1) average lookup, insert, and delete. Learn frequency counting and two-sum patterns.
Lessons
1. Intro
O(1) lookups
2. Vocabulary - Hash Table
Key-value storage
3. How Hashing Works
The basic idea
4. Hash Table Operations
Average vs worst case
5. Hash Set vs Hash Map
When to use which
6. Pattern - Frequency Counting
Counting occurrences
7. Frequency Counting Applications
Common uses
8. Problem - Valid Anagram
Frequency comparison
9. Valid Anagram - Algorithm
Two approaches
10. Valid Anagram - Implementation
Complete solution
11. Lessons from Valid Anagram
Frequency pattern
12. Quiz: Frequency Counting
Time complexity
13. The Pair Finding Problem
Beyond sorted arrays
14. Pattern - Complement Lookup
Find the other half
15. Problem - Two Sum
Classic hash map
16. Two Sum - Algorithm
One pass solution
17. Two Sum - Implementation
Complete solution
18. Lessons from Two Sum
Complement pattern
19. Quiz: Two Sum Pattern
Order of operations
20. Problem - Group Anagrams
Hash with custom keys
21. Group Anagrams - Key Design
Canonical form
22. Group Anagrams - Implementation
Complete solution
23. Lessons from Group Anagrams
Custom hash keys
24. Combining Techniques
Prefix sum meets hash
25. The Core Idea
Counting complements
26. Problem - Subarray Sum Equals K
Prefix + hash combo
27. Subarray Sum - Algorithm
Count as you go
28. Subarray Sum - Why Initialize with 0
Handling edge case
29. Subarray Sum - Implementation
Complete solution
30. Lessons from Subarray Sum
Combined power
31. Quiz: Prefix Sum + Hash
Initial value
32. A Harder Problem
Sequence detection
33. Longest Consecutive - The Idea
Start from sequence beginning
34. Longest Consecutive - Algorithm
Two-phase approach
35. Longest Consecutive - Implementation
Complete solution
36. Lessons from Longest Consecutive
Amortized thinking
37. Quiz: Hash Set Usage
Time analysis
38. When Hashing Fails
Collision attacks
39. Recognizing Hash Problems
Pattern signals
40. Section Recap
What we learned
Practice Problems
Classic introduction to hash maps for tracking username frequencies. Generate unique usernames by appending numbers.
Combines prefix sums with sliding window. Teaches frequency-based optimization fundamental to hash table applications.
Frequency counting combined with combinatorics. Use hash maps to find the k-th lexicographic pair efficiently.
Advanced use of multiset to track segment lengths dynamically. Teaches collision handling and efficient updates.
Perfect introduction to polynomial string hashing. Check if string with one character difference exists in a set.
Classic problem for counting distinct substrings using polynomial hashing. Demonstrates why double hashing prevents collisions.
Can be solved with KMP or string hashing. Find substring that appears as prefix, suffix, and middle.
Excellent for mastering rolling hash for suffix-prefix matching. Find longest overlap between consecutive strings.
01-trie problem for maximum XOR queries. Teaches binary representation hashing and greedy bit traversal.
Combines prefix sums with data structures. Hash-based discretization for counting subarrays with sum less than threshold.
Masterclass in binary trie for XOR queries. Handle dynamic insertions/deletions while counting elements satisfying conditions.
Advanced palindrome detection using bidirectional hashing. Compute hashes on both original and reversed strings.
The quintessential hash map problem teaching the fundamental pattern of O(1) lookups while iterating.
Core frequency counting pattern using hash maps to compare character distributions.
Advanced grouping pattern using sorted strings or character counts as hash keys for O(n) grouping.
Brilliant O(n) solution using hash sets to identify sequence starts and extend them.
The canonical prefix sum + hash map problem for counting subarrays in O(n) time.
Combines hash map with doubly linked list for O(1) operations on both access and eviction.
Hash map + dynamic array enabling O(1) random access. Teaches swap-with-last-element trick.
Meet-in-the-middle technique with hash maps reducing O(n^4) to O(n^2).