NeetCode #608LC-694MediumGraphsNC Algo100
← Back to All Problems#608 · #694 · Number of Distinct Islands(不同岛屿的数量)
📌 Problem Statement & Constraints
You are given an
m x n binary matrix grid. An island is a group of 1s connected 4-directionally. Two islands are considered the same if they have the same shape, regardless of position or rotation. Return the number of distinct island shapes. Constraints: 1 <= m, n <= 50.💡 Core Algorithmic Approaches
- For each island, record a canonical signature of its shape.
- The signature is the set of cell coordinates relative to the island's first cell, which is translation-invariant.
- Rotation and reflection are not considered the same here, so no further normalisation is needed.
- Storing the signatures in a set gives the number of distinct shapes.
💻 Benchmark Python3 Implementation
class Solution:
def numDistinctIslands(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
shapes = set()
def dfs(r: int, c: int, r0: int, c0: int, path: list) -> None:
if not (0 <= r < m and 0 <= c < n) or grid[r][c] != 1:
return
grid[r][c] = 0 # mark visited
path.append((r - r0, c - c0)) # coordinates relative to the origin cell
dfs(r + 1, c, r0, c0, path)
dfs(r - 1, c, r0, c0, path)
dfs(r, c + 1, r0, c0, path)
dfs(r, c - 1, r0, c0, path)
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
path = []
dfs(i, j, i, j, path)
shapes.add(tuple(sorted(path))) # canonical form
return len(shapes)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n log(m * n)): the sorting per island is bounded by its size.
💾 Space Complexity
O(m * n) for the signatures.
⚠️ Interview Pitfalls & Follow-ups
- Using absolute coordinates: two identical shapes at different positions would look different.
- Sorting the path instead of using DFS order: both work as canonical forms; sorting is more obviously translation-invariant.
- Treating rotations as identical: this problem does not (contrast with 711).
- Forgetting to mark visited: cells would be recounted within the same island.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.