Number of Distinct Islands
Medium · Graphs · Explanation and code example
Hash By Path Signature
How it works
Another way to uniquely identify an island's shape is through its dfs traversal path. If we always explore directions in the same order (e.g., Down, Up, Right, Left), two identical shapes will produce the same sequence of moves. We record each direction taken during dfs, and importantly, we also record when we backtrack. This backtrack marker is crucial because without it, different shapes could produce the same direction sequence.
Steps
- Use
dfsto explore each island, recording the direction of each move (D, U, R, L). - After exploring all neighbors from a cell, append a backtrack marker (e.g., "0").
- Convert the path signature to a string and add it to a set of unique islands.
- Return the size of the unique islands set.
Complexity
- Time complexity:
O(M × N) - Space complexity:
O(M × N)
Where
Mis the number of rows, andNis the number of columns
Things to watch for
Forgetting to Normalize Island Coordinates
When comparing islands, you must translate each island's cells relative to a consistent origin (typically the first cell discovered). Without normalization, two identical shapes at different positions in the grid will appear different, leading to overcounting distinct islands.
Missing Backtrack Markers in Path Signatures
When using path-based hashing, recording only the direction of each DFS move is insufficient. Different island shapes can produce identical direction sequences if backtracking is not recorded. Always append a marker (like "0") when returning from a recursive call to distinguish branching structures.
Using Mutable Data Structures as Hash Keys
In languages like Python, using a list or set directly as a dictionary key will cause errors. You must convert to an immutable type (like frozenset or tuple) before adding to a set of unique islands. Similarly, in Java, ensure your island representation implements proper hashCode() and equals() methods if using custom objects.
Python code example
from typing import List
class Solution:
def numDistinctIslands(self, grid: List[List[int]]) -> int:
# Do a DFS to find all cells in the current island.
def dfs(row, col, direction):
if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]):
return
if (row, col) in seen or not grid[row][col]:
return
seen.add((row, col))
path_signature.append(direction)
dfs(row + 1, col, "D")
dfs(row - 1, col, "U")
dfs(row, col + 1, "R")
dfs(row, col - 1, "L")
path_signature.append("0")
# Repeatedly start DFS's as long as there are islands remaining.
seen = set()
unique_islands = set()
for row in range(len(grid)):
for col in range(len(grid[0])):
path_signature = []
dfs(row, col, "0")
if path_signature:
unique_islands.add(tuple(path_signature))
return len(unique_islands)
C++ code example
class Solution {
private:
vector<vector<int>>* grid;
vector<vector<bool>> visited;
string currentIsland;
void dfs(int row, int col, char dir) {
if (row < 0 || col < 0 || row >= grid->size() || col >= (*grid)[0].size()) {
return;
}
if (visited[row][col] || (*grid)[row][col] == 0) {
return;
}
visited[row][col] = true;
currentIsland += dir;
dfs(row + 1, col, 'D');
dfs(row - 1, col, 'U');
dfs(row, col + 1, 'R');
dfs(row, col - 1, 'L');
currentIsland += '0';
}
public:
int numDistinctIslands(vector<vector<int>>& grid) {
this->grid = &grid;
visited = vector<vector<bool>>(grid.size(), vector<bool>(grid[0].size(), false));
unordered_set<string> islands;
for (int row = 0; row < grid.size(); row++) {
for (int col = 0; col < grid[0].size(); col++) {
currentIsland = "";
dfs(row, col, '0');
if (currentIsland.empty()) {
continue;
}
islands.insert(currentIsland);
}
}
return islands.size();
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.