Medium

Number of Distinct Islands

LAB

Return the number of distinct island shapes in a binary grid, considering translations equivalent.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      1,
      1,
      0,
      0
    ],
    [
      1,
      0,
      0,
      1
    ],
    [
      0,
      0,
      1,
      1
    ]
  ]
}

Output
2

FUNCTION SHAPE

grid: intMatrix→int

SOLUTION NOTE

Key Idea: We use DFS to record the path signature of each island starting from a fixed point (S for Start), marking movement directions (D, U, R, L), and using B for backtracking to ensure shapes with different traversal structures are distinguishable. This ensures only translation-equivalent shapes are treated the same.

Reveal reference solution +

pythonREFERENCE

def numDistinctIslands(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    seen = set()

    def dfs(r, c, direction, path):
        if 0 <= r < m and 0 <= c < n and grid[r][c] == 1:
            grid[r][c] = 0
            path.append(direction)
            dfs(r + 1, c, 'D', path)
            dfs(r - 1, c, 'U', path)
            dfs(r, c + 1, 'R', path)
            dfs(r, c - 1, 'L', path)
            path.append('B')  # Backtrack marker

    shapes = set()
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                path = []
                dfs(i, j, 'S', path)  # S = Start
                shapes.add(tuple(path))
    return len(shapes)

TimeO(m*n)

SpaceO(m*n)

Open on LeetCode ↗