LeetCode 711 - Number of Distinct Islands II

LeetCode Problem 711

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Sorting, Matrix, Hash Function

Solution

Problem Understanding

In this problem, we are given a binary matrix where each cell contains either 0 or 1. A value of 1 represents land, while 0 represents water. An island is formed by connecting adjacent land cells in the four cardinal directions: up, down, left, and right.

The task is not simply to count islands. Instead, we must determine how many distinct island shapes exist in the grid.

Two islands are considered identical if one can be transformed into the other using any combination of:

• Rotation by 90, 180, or 270 degrees
• Reflection across a horizontal or vertical axis

This means islands that look different in their original orientation may still represent the same shape after transformation.

The input size is relatively small, with both dimensions at most 50. Since the grid contains at most 2500 cells, we can afford to perform DFS or BFS traversals over the entire matrix and also perform geometric normalization on island coordinates.

A few important observations follow from the constraints and problem definition:

• Islands may contain only one cell.
• Multiple islands can share the same shape but appear in different locations.
• Translation does not matter, meaning identical shapes shifted elsewhere in the grid are still considered the same.
• Rotations and reflections must also be treated as equivalent.
• The grid is guaranteed to contain only valid binary values.

Several edge cases can easily break a naive implementation:

• Single-cell islands, because every transformation produces the same result.
• Symmetric islands, where multiple transformations collapse into identical coordinate sets.
• Islands with irregular shapes, where normalization must be done carefully.
• Different traversal orders during DFS, which can produce inconsistent coordinate sequences if not sorted properly.

The main challenge is therefore not island discovery, but generating a canonical representation of an island shape that remains identical across all valid rotations and reflections.

Approaches

Brute Force Approach

A brute force solution would first extract every island using DFS or BFS. For each island, we could explicitly compare it against all previously discovered islands.

To determine whether two islands are equivalent, we would generate all eight possible transformations:

1. Original
2. Rotate 90 degrees
3. Rotate 180 degrees
4. Rotate 270 degrees
5. Reflect horizontally
6. Reflect vertically
7. Reflect plus rotate 90 degrees
8. Reflect plus rotate 270 degrees

For every pair of islands, we would check whether any transformed version matches after normalization.

This approach is correct because it exhaustively tests all legal transformations. However, it becomes expensive because every new island may need to be compared against many previously discovered islands, and each comparison itself involves multiple coordinate transformations and sorting operations.

In the worst case, if there are many islands, pairwise comparison becomes inefficient.

Optimal Approach

The key insight is that we do not actually need to compare islands pairwise.

Instead, for each island, we can compute a canonical normalized form. Any two equivalent islands will produce exactly the same canonical representation.

The process works as follows:

1. Extract all coordinates belonging to an island.
2. Generate all eight transformations of those coordinates.
3. Normalize each transformation by shifting it so the smallest coordinate becomes (0, 0).
4. Sort the normalized coordinates.
5. Choose the lexicographically smallest representation among the eight possibilities.

This canonical representation uniquely identifies the island shape regardless of translation, rotation, or reflection.

Once we have canonical forms, the problem reduces to counting distinct strings or tuples in a hash set.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k² * s log s)	O(s)	Compares every island with every other island
Optimal	O(m * n * log s)	O(m * n)	Uses canonical normalization and hashing

Where:

• k is the number of islands
• s is the size of an island
• m * n is the total number of cells

Algorithm Walkthrough

1. Traverse the grid cell by cell.

Whenever we encounter a land cell (1) that has not been visited, we start a DFS traversal to collect all coordinates belonging to that island. 2. During DFS, record island coordinates relative to the starting cell.

Using relative coordinates removes dependence on absolute grid position. For example, if the first cell is (r0, c0), every other coordinate is stored as (r - r0, c - c0). 3. After collecting all coordinates for the island, generate all eight transformations.

For each point (x, y), the transformations are:

• ( x, y)
• ( x, -y)
• (-x, y)
• (-x, -y)
• ( y, x)
• ( y, -x)
• (-y, x)
• (-y, -x)

These collectively represent all rotations and reflections. 4. Normalize each transformed coordinate set.

Since translation does not matter, shift every transformed shape so its smallest coordinate becomes (0, 0).

This is done by subtracting the minimum row and minimum column values from all coordinates. 5. Sort the normalized coordinates.

DFS traversal order may differ between islands, even for identical shapes. Sorting guarantees a consistent ordering. 6. Convert the normalized coordinates into a tuple representation.

This makes the shape hashable and suitable for insertion into a set. 7. Select the lexicographically smallest transformed representation.

Multiple transformations correspond to the same island. Choosing the smallest one ensures all equivalent islands map to the same canonical form. 8. Insert the canonical representation into a set.

Since sets automatically eliminate duplicates, the final answer is simply the size of the set.

Why it works

Every island transformation preserves relative structure. By generating all legal transformations and selecting a unique canonical representation, we ensure that any two equivalent islands normalize to exactly the same form.

Translation differences disappear during normalization, traversal order differences disappear after sorting, and geometric equivalence is handled by transformation generation.

Therefore, two islands are counted as identical if and only if they belong to the same equivalence class under rotation and reflection.

Python Solution

from typing import List, Tuple

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

        visited = [[False] * cols for _ in range(rows)]

        def dfs(r: int, c: int, base_r: int, base_c: int,
                cells: List[Tuple[int, int]]) -> None:
            if (
                r < 0 or r >= rows or
                c < 0 or c >= cols or
                visited[r][c] or
                grid[r][c] == 0
            ):
                return

            visited[r][c] = True
            cells.append((r - base_r, c - base_c))

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

        def normalize(cells: List[Tuple[int, int]]) -> Tuple[Tuple[int, int], ...]:
            transformations = [[] for _ in range(8)]

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

                for i in range(8):
                    transformations[i].append(transformed[i])

            normalized_forms = []

            for shape in transformations:
                shape.sort()

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

                normalized = []

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

                normalized_forms.append(tuple(normalized))

            return min(normalized_forms)

        distinct_shapes = set()

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

                    canonical = normalize(cells)
                    distinct_shapes.add(canonical)

        return len(distinct_shapes)

The implementation begins by scanning the grid for unvisited land cells. Once a new island is found, DFS gathers all coordinates belonging to that island.

Coordinates are stored relative to the starting cell, which removes positional dependence immediately.

The normalize function is the core of the solution. It constructs all eight transformations of the island. Each transformed shape is sorted and shifted so that its smallest coordinate becomes (0, 0).

Because every equivalent island eventually produces the same lexicographically smallest normalized representation, inserting these canonical forms into a set automatically removes duplicates.

Finally, the size of the set is returned.

Go Solution

package main

import (
	"sort"
	"strconv"
	"strings"
)

func numDistinctIslands2(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	visited := make([][]bool, rows)
	for i := range visited {
		visited[i] = make([]bool, cols)
	}

	type Point struct {
		x int
		y int
	}

	var dfs func(int, int, int, int, *[]Point)

	dfs = func(r, c, baseR, baseC int, cells *[]Point) {
		if r < 0 || r >= rows || c < 0 || c >= cols {
			return
		}

		if visited[r][c] || grid[r][c] == 0 {
			return
		}

		visited[r][c] = true

		*cells = append(*cells, Point{r - baseR, c - baseC})

		dfs(r+1, c, baseR, baseC, cells)
		dfs(r-1, c, baseR, baseC, cells)
		dfs(r, c+1, baseR, baseC, cells)
		dfs(r, c-1, baseR, baseC, cells)
	}

	normalize := func(cells []Point) string {
		transformations := make([][]Point, 8)

		for _, p := range cells {
			x := p.x
			y := p.y

			transformed := []Point{
				{x, y},
				{x, -y},
				{-x, y},
				{-x, -y},
				{y, x},
				{y, -x},
				{-y, x},
				{-y, -x},
			}

			for i := 0; i < 8; i++ {
				transformations[i] = append(transformations[i], transformed[i])
			}
		}

		forms := make([]string, 0)

		for _, shape := range transformations {
			sort.Slice(shape, func(i, j int) bool {
				if shape[i].x == shape[j].x {
					return shape[i].y < shape[j].y
				}
				return shape[i].x < shape[j].x
			})

			minX := shape[0].x
			minY := shape[0].y

			var builder strings.Builder

			for _, p := range shape {
				builder.WriteString(
					strconv.Itoa(p.x-minX) +
						"," +
						strconv.Itoa(p.y-minY) +
						";",
				)
			}

			forms = append(forms, builder.String())
		}

		sort.Strings(forms)

		return forms[0]
	}

	distinct := make(map[string]bool)

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == 1 && !visited[r][c] {
				cells := []Point{}

				dfs(r, c, r, c, &cells)

				canonical := normalize(cells)

				distinct[canonical] = true
			}
		}
	}

	return len(distinct)
}

The Go implementation follows the same algorithmic structure as the Python version. Since Go tuples do not exist natively, island representations are encoded as strings.

Slices are used for coordinate storage, and sort.Slice provides lexicographic ordering for transformed coordinates.

Instead of Python's tuple hashing, Go uses a map[string]bool to track distinct canonical island forms.

Because coordinate values remain small, integer overflow is not a concern.

Worked Examples

Example 1

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

The first island is discovered at (0,0).

Relative coordinates collected by DFS:

Cell	Relative Coordinate
(0,0)	(0,0)
(0,1)	(0,1)
(1,0)	(1,0)

The second island is discovered at (2,4).

Relative coordinates:

Cell	Relative Coordinate
(2,4)	(0,0)
(3,4)	(1,0)
(3,3)	(1,-1)

After generating transformations and normalization, both islands produce the same canonical representation:

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

The set contains only one distinct shape.

Final answer:

1

Example 2

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

The first island coordinates:

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

The second island coordinates:

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

Both islands already match directly without transformation.

Canonical representation:

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

Only one distinct island exists.

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n * log s)	Each cell is visited once, and island normalization sorts transformed coordinates
Space	O(m * n)	Visited matrix, DFS recursion stack, and island storage

Here, s represents the size of the largest island.

The DFS traversal itself is linear in the number of cells. For each island, we generate eight transformed versions and sort their coordinates. Since the total number of island cells across the grid is bounded by m * n, the overall complexity remains efficient for the problem constraints.

Test Cases

from typing import List

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

        visited = [[False] * cols for _ in range(rows)]

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

            visited[r][c] = True
            cells.append((r - br, c - bc))

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

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

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

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

            forms = []

            for shape in transforms:
                shape.sort()

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

                normalized = []

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

                forms.append(tuple(normalized))

            return min(forms)

        shapes = set()

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

        return len(shapes)

sol = Solution()

# Example 1
assert sol.numDistinctIslands2([
    [1,1,0,0,0],
    [1,0,0,0,0],
    [0,0,0,0,1],
    [0,0,0,1,1]
]) == 1  # Rotation equivalence

# Example 2
assert sol.numDistinctIslands2([
    [1,1,0,0,0],
    [1,1,0,0,0],
    [0,0,0,1,1],
    [0,0,0,1,1]
]) == 1  # Identical square islands

# Single cell islands
assert sol.numDistinctIslands2([
    [1,0,1]
]) == 1  # All single-cell islands identical

# Completely different islands
assert sol.numDistinctIslands2([
    [1,1,0],
    [0,0,0],
    [0,1,1]
]) == 1  # Same horizontal domino shape

# Distinct shapes
assert sol.numDistinctIslands2([
    [1,1,0],
    [1,0,0],
    [0,0,1]
]) == 2  # L-shape and single-cell island

# Empty water grid
assert sol.numDistinctIslands2([
    [0,0],
    [0,0]
]) == 0  # No islands

# Reflection equivalence
assert sol.numDistinctIslands2([
    [1,0,0,1],
    [1,1,1,1]
]) == 1  # Mirrored L-shapes

# Large connected island
assert sol.numDistinctIslands2([
    [1,1],
    [1,1]
]) == 1  # One large island

# Different orientations of same shape
assert sol.numDistinctIslands2([
    [1,0,0],
    [1,1,1],
    [0,0,1]
]) == 1  # Rotational equivalence

Test Summary

Test	Why
Example 1	Verifies rotational equivalence
Example 2	Verifies direct shape equality
Single cell islands	Ensures trivial shapes normalize correctly
Horizontal dominoes	Confirms translation invariance
Distinct shapes	Verifies different structures are separated
Empty grid	Ensures zero-island handling
Reflection equivalence	Confirms mirrored islands are merged
Large square island	Tests connected multi-cell normalization
Rotated variants	Ensures rotational canonicalization works

Edge Cases

Single-Cell Islands

An island consisting of only one land cell is an important corner case because every rotation and reflection produces the same coordinate set. A buggy normalization routine might accidentally produce duplicate or malformed transformations for size-one islands.

This implementation handles the case naturally because all transformations normalize to ((0,0)), which is inserted only once into the set.

Symmetric Islands

Some islands are symmetric under certain rotations or reflections. For example, a square island remains unchanged after multiple transformations.

If the implementation does not sort and normalize coordinates consistently, symmetric islands may incorrectly generate multiple canonical forms.

The solution avoids this issue by sorting every transformed coordinate list and always selecting the lexicographically smallest representation.

Islands with Different DFS Traversal Orders

Two identical islands can be traversed in different orders depending on starting position or recursive visitation sequence.

Without sorting coordinates before comparison, identical shapes might appear different simply because coordinates were collected in different sequences.

The implementation fixes this by sorting every transformed shape before normalization and canonicalization, guaranteeing deterministic representations regardless of traversal order.