Number of Distinct Islands
Problem
Two islands are 'the same' if they have the same shape (translation-only). Count distinct shapes.
grid=[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]1def num_distinct_islands(grid):
m, n = len(grid), len(grid[0]); seen = set(); shapes = set()
def dfs(r, c, br, bc, shape):
if (r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0 or (r, c) in seen): return
seen.add((r, c)); shape.append((r - br, c - bc))
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): dfs(r + dr, c + dc, br, bc, shape)
for r in range(m):
for c in range(n):
if grid[r][c] == 1 and (r, c) not in seen:
shape = []; dfs(r, c, r, c, shape); shapes.add(tuple(shape))
return len(shapes)function numDistinctIslands(grid) {
const m = grid.length, n = grid[0].length;
const seen = new Set(); const shapes = new Set();
const dfs = (r, c, br, bc, shape) => {
const k = r + ',' + c;
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === 0 || seen.has(k)) return;
seen.add(k); shape.push((r - br) + ':' + (c - bc));
for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) dfs(r + dr, c + dc, br, bc, shape);
};
for (let r = 0; r < m; r++) for (let c = 0; c < n; c++)
if (grid[r][c] === 1 && !seen.has(r + ',' + c)) {
const shape = []; dfs(r, c, r, c, shape); shapes.add(shape.join('|'));
}
return shapes.size;
}int numDistinctIslands(int[][] grid) {
int m = grid.length, n = grid[0].length;
Set shapes = new HashSet<>();
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
if (grid[r][c] == 1) {
StringBuilder sb = new StringBuilder();
dfs(grid, r, c, r, c, sb, m, n);
shapes.add(sb.toString());
}
return shapes.size();
}
void dfs(int[][] g, int r, int c, int br, int bc, StringBuilder sb, int m, int n) {
if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] != 1) return;
g[r][c] = -1; sb.append(r - br).append(':').append(c - bc).append(',');
int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};
for (int[] d : D) dfs(g, r + d[0], c + d[1], br, bc, sb, m, n);
} void dfs(vector>& g, int r, int c, int br, int bc, string& s) {
int m = g.size(), n = g[0].size();
if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] != 1) return;
g[r][c] = -1; s += to_string(r - br) + ":" + to_string(c - bc) + ",";
int D[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
for (auto& d : D) dfs(g, r + d[0], c + d[1], br, bc, s);
}
int numDistinctIslands(vector>& grid) {
set shapes;
for (int r = 0; r < (int)grid.size(); r++) for (int c = 0; c < (int)grid[0].size(); c++)
if (grid[r][c] == 1) { string s; dfs(grid, r, c, r, c, s); shapes.insert(s); }
return shapes.size();
} Explanation
Here two islands are "the same" only when they have the identical shape after sliding (translation), with no rotation or flipping allowed. The trick is to record each island's shape as a list of relative offsets from a fixed anchor — that makes the description independent of where the island sits on the grid.
We scan the grid, and at every unvisited land cell we run a DFS. The first cell of the island becomes the anchor (br, bc), and for each cell we visit we append (r - br, c - bc) to the shape list. A seen set keeps us from revisiting cells.
The reason this works is subtle but important: because the DFS always explores neighbors in the same fixed order (down, up, right, left), two islands with the same geometry produce the exact same sequence of offsets. We turn each shape into a hashable value and drop it into a shapes set, which automatically removes duplicates.
Example: [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]] has two separate 2×2 blocks. Both yield the offset list {(0,0),(0,1),(1,0),(1,1)}, so the set keeps just one and the answer is 1.
The final count is len(shapes), the number of distinct shapes.