dsa1 min read
Number of Distinct Islands — DFS Shape Hashing
Count islands with distinct shapes. Encode each island's DFS traversal path as a string to capture shape, store in a set.
Read →
Hashing
6 articles
dsa2 min read
Find Duplicate Subtrees
Find all duplicate subtrees by serializing each subtree and using a hash map to detect duplicates.
Read →
dsa2 min read
Path Sum IV
Sum all root-to-leaf path sums in a tree encoded as 3-digit integers using a hashmap to decode tree structure.
Read →
dsa2 min read
Rabin-Karp — Rolling Hash for Pattern Matching and Substring Search
Rabin-Karp uses a rolling polynomial hash to match patterns in O(n+m) expected time. The key is updating the hash in O(1) as the window slides.
Read →
dsa2 min read
String Hashing — Polynomial Hash for O(1) Substring Comparison
Precompute polynomial prefix hashes to compare any two substrings in O(1). Enables O(n log n) LCP computation and O(n) duplicate detection.
Read →
dsa2 min read
Longest Common Substring — DP and Rolling Hash Approaches
Find the longest common substring between two strings. DP approach O(nm), binary search + rolling hash O((n+m) log(n+m)).
Read →