LeetCode 694: Number of Distinct Islands

Problem Restatement

We are given an m x n binary matrix grid.

A cell with value 1 is land.

A cell with value 0 is water.

An island is a group of land cells connected horizontally or vertically.

We need to count how many distinct island shapes exist in the grid.

Two islands are considered the same if one can be translated to match the other. Translation means moving the island up, down, left, or right. Rotation and reflection do not count.

Input and Output

Example function shape:

def numDistinctIslands(grid: list[list[int]]) -> int:
    ...

Examples

Example 1:

grid = [
    [1, 1, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [0, 0, 0, 1, 1],
    [0, 0, 0, 1, 0],
]

There are two islands.

The first island contains:

(0,0), (0,1), (1,0)

The second island contains:

(2,3), (2,4), (3,3)

They have the same shape. The second island is just the first island shifted down and right.

Answer:

1

Example 2:

grid = [
    [1, 1, 0, 1, 1],
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [1, 1, 0, 1, 1],
]

This grid contains islands with different shapes.

Answer:

3

First Thought: Count Islands

This looks similar to the standard number of islands problem.

We can scan the grid and start DFS whenever we find an unvisited land cell.

That counts how many islands exist, but this problem asks for how many different island shapes exist.

So we need to record each island’s shape.

Key Insight

Translation should not matter.

So absolute coordinates are not useful by themselves.

For example, these two islands are the same shape:

Island A:
(0,0), (0,1), (1,0)

Island B:
(2,3), (2,4), (3,3)

Their absolute positions differ, but their relative positions are the same.

For each island, choose its first DFS cell as a base cell:

base_row, base_col

For every land cell (r, c) in that island, record:

(r - base_row, c - base_col)

For Island A:

For Island B:

Both islands produce the same shape signature:

((0, 0), (0, 1), (1, 0))

So they count as one distinct island shape.

Algorithm

Use DFS and a set of shape signatures.

1. Create an empty set shapes.
2. Scan every cell in the grid.
3. When a land cell 1 is found:
   • Treat it as the base cell of a new island.
   • Run DFS to visit the entire island.
   • During DFS, record every cell’s relative coordinate from the base.
   • Mark visited cells by changing them to 0.
   • Convert the shape list to a tuple.
   • Add it to shapes.
4. Return len(shapes).

Why DFS Order Works

We add relative coordinates during DFS.

Since we scan the grid in a fixed order and explore neighbors in a fixed order, identical translated islands produce the same relative coordinate sequence.

Another robust option is to sort the relative coordinates before storing them. That makes the representation independent of traversal order.

In this guide, we sort before storing because it is simple and explicit.

Walkthrough

Consider:

grid = [
    [1, 1, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [0, 0, 0, 1, 1],
    [0, 0, 0, 1, 0],
]

First island starts at (0, 0).

DFS records:

[(0, 0), (0, 1), (1, 0)]

Add this tuple to the set.

Second island starts at (2, 3).

DFS records:

[(0, 0), (0, 1), (1, 0)]

This is the same tuple, so the set still has one shape.

Final answer:

1

Correctness

Each DFS starts only from an unvisited land cell.

The DFS visits exactly all land cells in that island because it follows all horizontal and vertical land connections.

It does not visit cells from other islands because water cells and grid boundaries stop the traversal.

For each visited cell, the algorithm records its coordinate relative to the island’s starting cell.

If two islands have the same shape under translation, then every cell in one island has a corresponding cell in the other island with the same relative coordinate. Therefore, both islands produce the same normalized shape signature.

If two islands produce the same normalized shape signature, then their cells match after shifting one island’s base cell to the other’s base cell. Therefore, the islands are the same under translation.

The set stores each distinct signature once.

So the size of the set is exactly the number of distinct island shapes.

Complexity

Let:

If we sort each island’s coordinates, the total sorting cost depends on island sizes. With fixed DFS order, sorting can be skipped. In practice, the traversal remains linear over the grid, with additional storage for shape signatures.

Implementation

class Solution:
    def numDistinctIslands(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        shapes = set()

        def dfs(r: int, c: int, base_r: int, base_c: int, shape: list[tuple[int, int]]) -> None:
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return

            if grid[r][c] == 0:
                return

            grid[r][c] = 0
            shape.append((r - base_r, c - base_c))

            dfs(r + 1, c, base_r, base_c, shape)
            dfs(r - 1, c, base_r, base_c, shape)
            dfs(r, c + 1, base_r, base_c, shape)
            dfs(r, c - 1, base_r, base_c, shape)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    shape = []
                    dfs(r, c, r, c, shape)
                    shapes.add(tuple(sorted(shape)))

        return len(shapes)

Code Explanation

We keep a set of unique island shapes:

shapes = set()

The DFS receives the current cell and the base cell of the island:

def dfs(r, c, base_r, base_c, shape):

If the cell is outside the grid or water, stop:

if r < 0 or r >= rows or c < 0 or c >= cols:
    return

if grid[r][c] == 0:
    return

We mark land as visited by changing it to water:

grid[r][c] = 0

Then we record its relative coordinate:

shape.append((r - base_r, c - base_c))

After DFS finishes, the island shape is converted into an immutable tuple:

shapes.add(tuple(sorted(shape)))

At the end:

return len(shapes)

returns the number of distinct shapes.

Testing

def run_tests():
    s = Solution()

    grid = [
        [1, 1, 0, 0, 0],
        [1, 0, 0, 0, 0],
        [0, 0, 0, 1, 1],
        [0, 0, 0, 1, 0],
    ]
    assert s.numDistinctIslands(grid) == 1

    grid = [
        [1, 1, 0, 1, 1],
        [1, 0, 0, 0, 0],
        [0, 0, 0, 0, 1],
        [1, 1, 0, 1, 1],
    ]
    assert s.numDistinctIslands(grid) == 3

    grid = [
        [1, 0],
        [0, 1],
    ]
    assert s.numDistinctIslands(grid) == 1

    grid = [
        [0, 0],
        [0, 0],
    ]
    assert s.numDistinctIslands(grid) == 0

    grid = [
        [1, 1, 1],
        [0, 1, 0],
        [0, 1, 0],
    ]
    assert s.numDistinctIslands(grid) == 1

    print("all tests passed")

run_tests()

Test meaning: