Number of Distinct Islands
Understanding the Problem
We're given a 2D grid of 0s and 1s. Groups of connected 1s form islands, and we need to count how many distinct shapes exist. Two islands have the same shape if you can slide one on top of the other (translation only, no rotation or flipping).
The difference from the classic "Number of Islands" problem is that counting islands is not enough. We need to identify their shapes and group identical ones together. The real question is how to represent an island's shape in a way that lets us compare two islands for equality.
If we normalize each island's coordinates relative to a fixed reference point (the top-left cell of the island), two islands with the same shape produce the same set of normalized coordinates. That gives us a way to hash island shapes and use a set to count distinct ones.
Key Constraints:
1 <= m, n <= 50→ The grid holds at most 2,500 cells, so the time budget is generous. The choice between approaches comes down to how we represent a shape, not raw asymptotic limits.grid[i][j]is either0or1→ A standard binary grid with no special values to handle.
Approach 1: DFS with Coordinate Normalization
Intuition
Finding islands in a grid is a standard DFS/BFS problem. We scan the grid, and whenever we reach an unvisited 1, we start a traversal to discover all cells belonging to that island.
The new challenge is deciding whether two islands have the same shape. If we record the coordinates of every cell in an island and then shift all coordinates so the top-left corner of the island sits at (0, 0), two islands with the same shape produce the same set of normalized coordinates. Subtracting the minimum row and minimum column cancels out the island's absolute position, leaving only its shape.
For example, an L-shaped island at positions (2,3), (3,3), (3,4) and the same L-shape at (5,1), (6,1), (6,2) both normalize to {(0,0), (1,0), (1,1)}. Same normalized set means same shape.
The plan: find each island via DFS, normalize its coordinates, store the normalized shape in a set, and return the size of the set.
Algorithm
- Initialize a
visitedmatrix and an empty set to store distinct island shapes. - Scan the grid cell by cell. When we find an unvisited
1, start a DFS to collect all cells of that island. - After collecting all cells, normalize the coordinates by subtracting the minimum row and minimum column from each cell.
- Convert the normalized coordinates into a canonical form (sorted list of tuples) and add it to the set.
- After scanning the entire grid, return the size of the set.
Example Walkthrough
Code
- Time Complexity: O(m n log(m n)). We visit every cell at most once during DFS: O(m n). For each island of size k, sorting its normalized coordinates takes O(k log k). The total sorting work across all islands is bounded by O(m n log(m n)).
- Space Complexity: O(m n). The visited matrix takes O(m n). The cells list and shapes set together use at most O(m * n) space.
This approach collects coordinates, normalizes them, and sorts each island's cells. The next approach removes the normalization and sorting step by encoding the shape directly during the DFS traversal.
Approach 2: DFS with Path Signature (Optimal)
Intuition
Instead of recording where each cell is and normalizing afterward, we can record how we reached each cell. If two islands have the same shape and we always start the DFS from the first cell we encounter in the scan order (the top-most, then left-most cell), the DFS follows the same sequence of moves on both.
We encode each DFS traversal as a string of directions: 'D' for down, 'U' for up, 'R' for right, 'L' for left. Two islands with identical shapes produce identical direction strings.
There is one subtlety. We also need to record when a branch returns without finding land. Without backtrack markers, two different shapes can produce the same sequence of direction characters. Adding a 'B' marker when a DFS branch returns captures the tree structure of the traversal, not only the sequence of successful moves.
DFS is deterministic. Given the same shape and a fixed neighbor order (down, up, right, left), the traversal takes the same sequence of steps on any two identical islands, regardless of their position in the grid. We record relative moves, not absolute coordinates, so the start position drops out.
The backtrack markers separate DFS trees that share the same set of moves but branch differently. Consider two shapes both reachable with one 'D' and one 'R'. In one shape the DFS goes down, returns, then goes right from the start cell, giving S D B R B B. In another the DFS goes down and then right from the cell below, giving S D R B B B. Without the 'B' markers both collapse to S D R, so distinct shapes would hash to the same string. The markers record where each branch ends, which fixes the tree structure.
Algorithm
- Scan the grid for unvisited
1s. When found, start a DFS and record 'S' for the start cell. - On entering a new land cell, append the direction taken to reach it (D, U, R, L). Calls that land on water, the boundary, or a visited cell return immediately and append nothing.
- After a cell has tried all four neighbors, append a backtrack marker 'B' before returning.
- The resulting string is the island's shape signature.
- Add the signature to a set. Return the set's size.
Example Walkthrough
Code
- Time Complexity: O(m n). Each cell is visited at most once during the DFS. Building the path string takes O(1) per cell. Inserting into the hash set takes O(k) per island where k is the island size, but the total across all islands is O(m n).
- Space Complexity: O(m n). The visited matrix is O(m n). The path string and recursion stack can each go up to O(m * n) in the worst case.