LeetCode 711: Number of Distinct Islands II
A clear explanation of counting distinct island shapes under rotation and reflection using normalization and geometric transformations.
56 notes
A clear explanation of counting distinct island shapes under rotation and reflection using normalization and geometric transformations.
Find all missing numbers from 1 to n in O(n) time using in-place index marking.
Find all duplicated numbers in an array in O(n) time and O(1) extra space using index marking.
Hash table lookup strategies, open-addressing and chaining variants, probabilistic filters (Bloom, Cuckoo, XOR), and locality-sensitive similarity search.
Retrieve rows by probing a hash-based index structure using an exact key match.
Find matching records during a join by probing a hash table built from one relation.
Search for a pattern in text by comparing rolling hash values before verifying matching windows.
Resolve hash collisions by storing multiple elements in buckets using linked structures.
Retrieve a value by computing a hash and probing a table for the corresponding key.
Search for a pattern in a sequence by maintaining a hash over a sliding window.
Estimate set similarity and find similar items using compact MinHash signatures and banding.
Find near duplicate documents by comparing compact SimHash fingerprints under Hamming distance.
Search for approximate nearest neighbors by hashing similar items into the same buckets with high probability.
Map a key to the node that receives the highest hash score for that key.
Map a key to a node by placing both on a hash ring and selecting the next node clockwise.
Test approximate membership using a compact XOR-based filter with improved construction and cache locality.
Test approximate membership with a static fingerprint filter built from three hash locations and XOR constraints.
Test approximate membership by storing compact fingerprints in cuckoo hash table buckets.
Test approximate membership by splitting a hash fingerprint into quotient and remainder fields.
Test membership with a Bloom filter variant that supports deletions using small counters instead of bits.
Test set membership with a compact probabilistic bit array that allows false positives but no false negatives.
Look up a key using a collision free hash function that maps a static key set to exactly n table positions.
Look up a key in a static hash table whose hash function has no collisions for the stored key set.
Search in an open addressing hash table that keeps probe distances balanced across keys.
Search in a hash table that maintains elements within a small neighborhood of their home bucket.
Look up a key in a cuckoo hash table by checking a small fixed set of candidate positions.
Resolve hash collisions using a second hash function to define probe steps.
Resolve hash collisions by probing with quadratic offsets to reduce clustering.
Resolve hash collisions by scanning sequential slots until the key is found or an empty slot appears.
Examine hash-based structures in complete systems: streaming pipelines, graph algorithms, caches, and distributed workflows.
Choose and implement hash tables that perform reliably under mixed key types, uneven access patterns, and adversarial input.
Design hash table layouts that minimize cache misses and align memory access patterns with hardware behavior.
Combine hash tables with other data structures to handle skewed distributions, heavy deletions, and mixed workloads.
Achieve predictable worst-case bounds for hash-based structures rather than relying solely on average-case expectations.
Verify correctness, stability, and performance of hash-based structures through randomized and adversarial test strategies.
Produce stable hash values that remain consistent across program runs, machines, builds, and language runtimes.
Defend hash tables against adversarial inputs that force worst-case collision behavior using randomized hashing.
Understand how memory hierarchy effects cause hash table performance to deviate from asymptotic expectations.
Remove duplicate entries from a dataset or stream efficiently using hash sets for membership tracking.
Join two collections by key using a hash table to reduce the cost from quadratic to linear expected time.
Distribute keys across a dynamic set of nodes so that adding or removing nodes moves only a minimal fraction of keys.
Approximate frequency counting for large key streams using a compact probabilistic data structure with bounded error.
Test set membership approximately using a compact bit array and multiple hash functions, with no false negatives and bounded false positives.
Compute hash values for sliding windows over a sequence in constant time by incrementally updating rather than recomputing.
Hash and compare multi-field keys correctly by combining all fields that participate in equality into the hash function.
Partition a collection into groups by key using a hash map that accumulates values into per-key lists or sets.
Track frequency counts for keys using a hash map that increments a counter on each insertion of an existing key.
Build a hash-based map that associates keys with values and supports insert, lookup, delete, and update in expected constant time.
Implement a hash-based set for fast membership testing, insertion, and deletion without associated values.
Rebuild a hash table's bucket array after resizing so that every stored key satisfies the placement invariant for the new capacity.
Control hash table performance by monitoring the load factor and growing the bucket array before collisions accumulate.
Resolve hash collisions using separate chaining or open addressing, with trade-offs in memory, locality, and load tolerance.
Design and evaluate hash functions that distribute keys uniformly across buckets while remaining fast to compute.
A data structure that supports fast insertion, lookup, and deletion by mapping keys to bucket positions via a hash function.
Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly.
Hash tables, hash functions, collision handling, probabilistic structures, and practical design for constant-time key-value access.