⚡Flashcard Drill➔
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

  1. For each island, generate all 8 symmetries (4 rotations × 2 reflections) of its cell set.
  2. Normalise each by translating so the minimum row and column are 0.
  3. The canonical form is the lexicographically smallest of the 8 normalised sets.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems