Number of Distinct Islands II - Solution & Explanation

Problem Overview: You are given a binary grid where 1 represents land and 0 represents water. An island is a group of connected land cells. Two islands are considered the same if one can be rotated or reflected to match the other. The task is to count how many distinct island shapes exist under these transformations.

Approach 1: Pairwise Shape Comparison (Brute Force) (Time: O(I² * K), Space: O(I * K))

Run Depth-First Search to extract the coordinates of every island. Store each island as a list of relative positions from its starting cell. To determine if two islands are the same, generate all 8 transformations (4 rotations and their reflections) of one island and check if any match the other after normalization. This requires comparing each island with every previously found island. The approach works conceptually but becomes slow when many islands exist because every comparison requires transformation and coordinate matching.

Approach 2: Canonical Shape Hashing with DFS (Optimal) (Time: O(m * n * K), Space: O(m * n))

Traverse the grid and run DFS for every unvisited land cell. Record the island's coordinates relative to the origin cell. For that set of coordinates, generate the 8 possible transformations representing rotations and reflections. Normalize each transformation by shifting coordinates so the smallest x and y become zero, then sort the points and serialize them into a string. Choose the lexicographically smallest representation as the island's canonical form. Store this canonical shape in a hash table. Because every equivalent island produces the same canonical signature, duplicates collapse automatically. The number of unique signatures in the set is the answer.

The key insight is canonicalization. Instead of comparing islands against each other, convert every island into a transformation-invariant representation. DFS collects the structure, transformations normalize orientation, and hashing provides constant-time uniqueness checks. You could also explore component detection with Breadth-First Search, but DFS is typically simpler for collecting relative coordinates.

Recommended for interviews: The canonical hashing approach with DFS is the expected solution. Interviewers want to see that you recognize rotational/reflection symmetry and convert shapes into a normalized representation. Explaining the brute-force comparison first shows understanding of the equivalence rule, while the hashing approach demonstrates strong algorithm design and practical use of transformations and hash sets.