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

  1. For each island, record a canonical signature of its shape.
  2. The signature is the set of cell coordinates relative to the island's first cell, which is translation-invariant.
  3. Rotation and reflection are not considered the same here, so no further normalisation is needed.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems