LeetCode 711: Number of Distinct Islands II

Problem Restatement

We are given a binary grid.

An island is a group of connected land cells using 4-directional movement:

up
down
left
right

We need to count how many distinct island shapes exist.

Two islands are considered the same if one can be transformed into the other using:

This means two islands are identical if we can rotate or flip one island and then shift it to overlap perfectly with the other.

Input and Output

The function shape is:

class Solution:
    def numDistinctIslands2(self, 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:

Island A:
1 1
1

Island B:
1 1
1

One island can be rotated to match the other.

So the answer is:

1

Example 2:

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

Some islands match after transformations, while others do not.

The answer is:

2

First Thought: Compare Coordinates Directly

We can use DFS or BFS to collect all cells of an island.

For example:

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

Then shift the coordinates so the smallest point becomes (0,0).

This handles translation.

However, this is not enough.

Two islands may match after rotation or reflection.

For example:

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

and:

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

are the same after rotation.

So direct coordinate comparison fails.

Key Insight

Every island can generate up to 8 transformed versions:

For each island:

1. Generate all 8 transformations.
2. Normalize each transformation by translation.
3. Convert each normalized form into a comparable representation.
4. Choose the lexicographically smallest representation as the canonical form.

If two islands have the same canonical form, then they are equivalent under allowed transformations.

Geometry Transformations

Suppose a point is:

(x, y)

The 8 transformations are:

These cover every rotation and mirror symmetry.

Algorithm

Traverse the grid.

Whenever we find an unvisited land cell:

1. Run DFS to collect all coordinates of that island.
2. Generate all 8 transformations.
3. Normalize each transformed island:
   • Sort coordinates.
   • Shift them so the smallest coordinate becomes (0,0).
4. Convert each normalized transformation into a tuple.
5. Choose the smallest tuple lexicographically.
6. Add that canonical representation to a set.

At the end, return the size of the set.

Correctness

The DFS correctly collects every cell belonging to one connected island because it recursively visits all reachable land cells using 4-directional movement and marks them as visited.

For any island, the algorithm generates all possible rotations and reflections. Therefore, if another island is equivalent under the allowed transformations, one of the generated transformed versions must match it geometrically.

Normalization removes translation differences. After shifting coordinates so the smallest point becomes (0,0), two transformed islands that have the same shape will produce identical normalized coordinate sets.

The canonical form is chosen as the lexicographically smallest normalized transformation. Since every equivalent island generates the same set of transformed normalized shapes, all equivalent islands produce the same canonical form.

Non-equivalent islands cannot produce the same canonical form, because that would mean one transformation aligns them exactly, contradicting non-equivalence.

Therefore:

1. Equivalent islands map to the same canonical representation.
2. Non-equivalent islands map to different canonical representations.

So the number of distinct canonical forms equals the number of distinct island shapes.

Complexity

Suppose:

m = number of rows
n = number of columns
k = size of one island

More precisely:

• DFS visits every cell once.
• Each island generates 8 transformations.
• Each transformation sorts up to k coordinates.

The total remains acceptable for the problem constraints.

Implementation

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

        visited = set()
        shapes = set()

        def dfs(r, c, cells):
            if (
                r < 0
                or r >= rows
                or c < 0
                or c >= cols
                or grid[r][c] == 0
                or (r, c) in visited
            ):
                return

            visited.add((r, c))
            cells.append((r, c))

            dfs(r + 1, c, cells)
            dfs(r - 1, c, cells)
            dfs(r, c + 1, cells)
            dfs(r, c - 1, cells)

        def normalize(cells):
            transforms = [[] for _ in range(8)]

            for x, y in cells:
                candidates = [
                    (x, y),
                    (y, -x),
                    (-x, -y),
                    (-y, x),
                    (x, -y),
                    (y, x),
                    (-x, y),
                    (-y, -x),
                ]

                for i in range(8):
                    transforms[i].append(candidates[i])

            normalized_forms = []

            for shape in transforms:
                shape.sort()

                min_x = shape[0][0]
                min_y = shape[0][1]

                shifted = []

                for x, y in shape:
                    shifted.append((x - min_x, y - min_y))

                normalized_forms.append(tuple(shifted))

            return min(normalized_forms)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1 and (r, c) not in visited:
                    cells = []

                    dfs(r, c, cells)

                    shapes.add(normalize(cells))

        return len(shapes)

Code Explanation

The outer loops scan the grid:

for r in range(rows):
    for c in range(cols):

When we find unvisited land, we collect the island:

cells = []
dfs(r, c, cells)

DFS adds coordinates into cells:

cells.append((r, c))

The normalize function generates all 8 transformations:

candidates = [
    (x, y),
    (y, -x),
    (-x, -y),
    (-y, x),
    (x, -y),
    (y, x),
    (-x, y),
    (-y, -x),
]

Each transformed version is sorted:

shape.sort()

Then shifted so the smallest coordinate becomes (0,0):

shifted.append((x - min_x, y - min_y))

Finally, we choose the smallest normalized representation:

return min(normalized_forms)

This canonical form uniquely identifies the island shape.

Example Walkthrough

Suppose an island has coordinates:

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

One transformation gives:

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

After sorting and shifting:

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

Another island with this shape after normalization will produce the same canonical tuple.

Therefore both islands are counted as one distinct shape.

Testing

def test_num_distinct_islands_2():
    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.numDistinctIslands2(grid) == 1

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

    assert s.numDistinctIslands2(grid) == 2

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

    assert s.numDistinctIslands2(grid) == 1

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

    assert s.numDistinctIslands2(grid) == 1

    print("all tests passed")

test_num_distinct_islands_2()

Test coverage: