NeetCode #625LC-711HardGraphs
← Back to All Problems#625 · #711 · Number of Distinct Islands II(不同岛屿的数量 II)
📌 Problem Statement & Constraints
You are given an
m x n binary matrix grid. Two islands are considered the same if one can be translated, rotated by 90/180/270 degrees, or reflected to match the other. Return the number of distinct island shapes. Constraints: 1 <= m, n <= 50.💡 Core Algorithmic Approaches
- For each island, generate all 8 symmetries (4 rotations × 2 reflections) of its cell set.
- Normalise each by translating so the minimum row and column are 0.
- The canonical form is the lexicographically smallest of the 8 normalised sets.
- Counting distinct canonical forms gives the answer.
💻 Benchmark Python3 Implementation
class Solution:
def numDistinctIslands2(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
shapes = set()
def dfs(r: int, c: int, path: list) -> None:
if not (0 <= r < m and 0 <= c < n) or grid[r][c] != 1:
return
grid[r][c] = 0
path.append((r, c))
dfs(r + 1, c, path)
dfs(r - 1, c, path)
dfs(r, c + 1, path)
dfs(r, c - 1, path)
def canonical(path: list) -> tuple:
forms = []
for t in range(8): # 4 rotations x 2 reflections
pts = []
for x, y in path:
if t == 0: pts.append((x, y))
elif t == 1: pts.append((x, -y))
elif t == 2: pts.append((-x, y))
elif t == 3: pts.append((-x, -y))
elif t == 4: pts.append((y, x))
elif t == 5: pts.append((y, -x))
elif t == 6: pts.append((-y, x))
else: pts.append((-y, -x))
# translate so the minimum coordinates are 0
minx = min(p[0] for p in pts)
miny = min(p[1] for p in pts)
forms.append(tuple(sorted((p[0] - minx, p[1] - miny) for p in pts)))
return min(forms) # canonical = lexicographically smallest
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
path = []
dfs(i, j, path)
shapes.add(canonical(path))
return len(shapes)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n * 8 log(m * n)): the 8 symmetries are a constant factor.
💾 Space Complexity
O(m * n) for the canonical forms.
⚠️ Interview Pitfalls & Follow-ups
- Only applying rotations: reflections are also allowed, so 8 symmetries are needed.
- Forgetting the translation normalisation: shapes at different positions would differ.
- Using DFS order as the canonical form: rotations change the DFS order, so it is not invariant.
- Confusing this with 694: there, rotations and reflections produce different islands.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.