LeetCode 694 - Number of Distinct Islands

The problem gives us a binary matrix called grid, where each cell contains either 0 or 1. A value of 1 represents land, and a value of 0 represents water. An island is formed by connecting adjacent land cells in the four cardinal directions: up, down, left, and right.

leetcodemediumarrayhash-tabledepth-first-searchbreadth-first-searchunion-findsortingmatrixhash-function

LeetCode Problem 694

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

Solution

Problem Understanding

The problem gives us a binary matrix called grid, where each cell contains either 0 or 1. A value of 1 represents land, and a value of 0 represents water. An island is formed by connecting adjacent land cells in the four cardinal directions: up, down, left, and right. Diagonal connections do not count.

The goal is not simply to count how many islands exist. Instead, we must determine how many distinct island shapes appear in the grid. Two islands are considered identical if one can be shifted, or translated, to overlap exactly with the other. Rotation and reflection are not allowed.

This distinction is extremely important. Consider two L-shaped islands. If one is rotated relative to the other, they are considered different because only translation is permitted. However, if two islands have exactly the same arrangement of cells relative to their starting point, they count as the same shape even if they appear in different locations in the grid.

The input constraints are relatively small:

  • 1 <= m, n <= 50
  • The grid contains only 0 and 1

Since the grid can contain at most 2500 cells, a full traversal of the matrix is completely feasible. This strongly suggests that graph traversal algorithms such as Depth-First Search (DFS) or Breadth-First Search (BFS) are appropriate.

Several edge cases are important to recognize immediately. A grid with no land should return 0. A grid where every island has a unique shape should count each separately. Multiple islands that are identical but located in different positions should only contribute once to the final answer. Another subtle case is when two islands contain the same number of cells but have different structures. In that situation, they must still be considered distinct.

Approaches

A brute-force approach would first identify every island in the grid and store the coordinates of all its cells. Then, for every newly discovered island, we could compare it against every previously discovered island to determine whether their shapes match after translation.

To compare two islands, we would normalize their coordinates by subtracting the position of a reference cell, usually the first discovered land cell. If the normalized coordinate sets match exactly, then the islands are identical.

This approach is correct because normalization removes the effect of position while preserving the island's structure. However, repeatedly comparing islands against one another becomes inefficient as the number of islands grows. In the worst case, many islands may exist, and each comparison may involve many cells.

The key insight for a more efficient solution is that every island can be converted directly into a canonical representation during traversal. Instead of comparing islands pairwise, we compute a unique signature for each island and insert that signature into a hash set. Since sets automatically eliminate duplicates, the number of unique signatures equals the number of distinct islands.

The most common canonical representation is a list of relative coordinates. While traversing an island, we record each cell's position relative to the island's starting cell. Two islands with identical shapes will produce identical relative coordinate lists regardless of where they appear in the grid.

Approach Time Complexity Space Complexity Notes
Brute Force O(k² * s) O(k * s) Compare every island against previously discovered islands
Optimal O(m * n) O(m * n) Use DFS/BFS and store normalized island shapes in a hash set

Here:

  • k is the number of islands
  • s is the average island size
  • m * n is the total number of cells in the grid

Algorithm Walkthrough

  1. Initialize a set called distinct_shapes.

This set will store the canonical representation of every unique island shape. Since sets automatically remove duplicates, identical islands will only appear once. 2. Create a visited structure or modify the grid in place.

We need to ensure each land cell is processed exactly once. Without tracking visited cells, DFS could repeatedly revisit the same locations and potentially enter infinite recursion. 3. Traverse every cell in the grid.

For each position (row, col):

  • If the cell is water (0), skip it.
  • If the cell has already been visited, skip it.
  • Otherwise, we have found a new island.
  1. Start a DFS from the current land cell.

Record the starting position as (base_row, base_col). This becomes the reference point used for normalization. 5. During DFS, record relative coordinates.

For every visited land cell (r, c), compute:

(r - base_row, c - base_col)

These relative offsets describe the island's shape independently of its absolute location. 6. Explore all four directions.

From each cell, recursively visit:

  • Up
  • Down
  • Left
  • Right

Only continue traversal if the neighbor is inside the grid, contains land, and has not yet been visited. 7. Store the completed shape.

After DFS finishes, convert the collected relative coordinates into an immutable structure such as a tuple. Insert this tuple into distinct_shapes. 8. Continue scanning the grid.

Repeat the process for every unvisited land cell until the entire matrix has been processed. 9. Return the size of the set.

The number of distinct canonical representations equals the number of distinct island shapes.

Why it works

The algorithm works because translation affects only absolute coordinates, not relative coordinates. By storing every cell relative to the island's starting position, we eliminate positional differences while preserving structural differences. Therefore, two islands generate identical signatures if and only if they have exactly the same shape under translation.

Python Solution

from typing import List, Tuple, Set

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

        visited = set()
        distinct_shapes: Set[Tuple[Tuple[int, int], ...]] = set()

        def dfs(r: int, c: int,
                base_r: int,
                base_c: int,
                shape: List[Tuple[int, int]]) -> None:

            visited.add((r, c))

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

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

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if (
                    0 <= nr < rows and
                    0 <= nc < cols and
                    grid[nr][nc] == 1 and
                    (nr, nc) not in visited
                ):
                    dfs(nr, nc, base_r, base_c, shape)

        for row in range(rows):
            for col in range(cols):

                if grid[row][col] == 1 and (row, col) not in visited:

                    shape = []

                    dfs(row, col, row, col, shape)

                    distinct_shapes.add(tuple(shape))

        return len(distinct_shapes)

The implementation begins by determining the grid dimensions and initializing two important structures: a visited set and a distinct_shapes set.

The visited set ensures that each land cell is processed only once. The distinct_shapes set stores normalized island representations. Each representation is stored as a tuple because tuples are immutable and hashable, making them valid set elements.

The dfs helper function performs the island traversal. It receives the current cell, the base coordinates of the island, and the shape list currently being constructed.

Whenever DFS visits a new land cell, it computes the relative coordinate:

(current_row - base_row, current_col - base_col)

This normalization step is the core of the algorithm because it removes positional differences between islands.

The DFS then explores the four neighboring directions. Boundary checks ensure we remain inside the grid, and the visited check prevents duplicate traversal.

In the main traversal loop, every unvisited land cell starts a new DFS. After traversal completes, the generated shape is converted into a tuple and inserted into the set of distinct shapes.

Finally, the algorithm returns the number of unique shapes stored in the set.

Go Solution

package main

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

	visited := make(map[[2]int]bool)
	distinctShapes := make(map[string]bool)

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

	dfs = func(r, c, baseR, baseC int, shape *[][2]int) {
		visited[[2]int{r, c}] = true

		*shape = append(*shape, [2]int{r - baseR, c - baseC})

		directions := [][2]int{
			{1, 0},
			{-1, 0},
			{0, 1},
			{0, -1},
		}

		for _, dir := range directions {
			nr := r + dir[0]
			nc := c + dir[1]

			if nr >= 0 &&
				nr < rows &&
				nc >= 0 &&
				nc < cols &&
				grid[nr][nc] == 1 &&
				!visited[[2]int{nr, nc}] {

				dfs(nr, nc, baseR, baseC, shape)
			}
		}
	}

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {

			if grid[r][c] == 1 && !visited[[2]int{r, c}] {

				shape := make([][2]int, 0)

				dfs(r, c, r, c, &shape)

				shapeKey := ""

				for _, point := range shape {
					shapeKey += string(rune(point[0]+100)) + "," +
						string(rune(point[1]+100)) + ";"
				}

				distinctShapes[shapeKey] = true
			}
		}
	}

	return len(distinctShapes)
}

The Go implementation follows the same algorithmic structure as the Python version, but several language-specific details differ.

Go does not support tuples directly, so coordinate pairs are represented using fixed-size arrays like [2]int.

Since slices are mutable but passed by value, the DFS function receives a pointer to the shape slice so modifications persist across recursive calls.

Go maps require comparable keys. Because slices are not comparable, the island shape must be serialized into a string before insertion into the distinctShapes map. This string acts as the canonical representation of the island.

Integer overflow is not a concern here because grid dimensions are very small, with maximum coordinate offsets well below Go's integer limits.

Worked Examples

Example 1

Input:

[
  [1,1,0,0,0],
  [1,1,0,0,0],
  [0,0,0,1,1],
  [0,0,0,1,1]
]

The grid contains two islands.

First Island Traversal

Starting cell: (0,0)

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

Generated shape:

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

This shape is inserted into the set.

Second Island Traversal

Starting cell: (2,3)

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

Generated shape:

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

This matches the first island's signature exactly.

Final set contents:

{
  [(0,0), (0,1), (1,0), (1,1)]
}

Answer:

1

Example 2

Input:

[
  [1,1,0,1,1],
  [1,0,0,0,0],
  [0,0,0,0,1],
  [1,1,0,1,1]
]

Island 1

Starting at (0,0):

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

Shape:

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

Island 2

Starting at (0,3):

Visited Cell Relative Coordinate
(0,3) (0,0)
(0,4) (0,1)

Shape:

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

Island 3

Starting at (2,4):

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

Shape:

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

Island 4

Starting at (3,0):

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

Shape:

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

This matches Island 2.

Final distinct shapes:

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

Answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Every cell is visited at most once
Space O(m * n) Visited set and shape storage may contain all cells

The DFS traversal processes each cell exactly one time. Each visit performs constant-time operations, so the total runtime is proportional to the number of cells in the grid.

The space complexity comes primarily from the visited structure, recursion stack, and stored island shapes. In the worst case, the entire grid may consist of land, requiring storage proportional to all cells.

Test Cases

from typing import List

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

        visited = set()
        distinct_shapes = set()

        def dfs(r, c, base_r, base_c, shape):
            visited.add((r, c))
            shape.append((r - base_r, c - base_c))

            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr, nc = r + dr, c + dc

                if (
                    0 <= nr < rows and
                    0 <= nc < cols and
                    grid[nr][nc] == 1 and
                    (nr, nc) not in visited
                ):
                    dfs(nr, nc, base_r, base_c, shape)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1 and (r, c) not in visited:
                    shape = []
                    dfs(r, c, r, c, shape)
                    distinct_shapes.add(tuple(shape))

        return len(distinct_shapes)

solution = Solution()

assert solution.numDistinctIslands([
    [1,1,0,0,0],
    [1,1,0,0,0],
    [0,0,0,1,1],
    [0,0,0,1,1]
]) == 1  # identical square islands

assert solution.numDistinctIslands([
    [1,1,0,1,1],
    [1,0,0,0,0],
    [0,0,0,0,1],
    [1,1,0,1,1]
]) == 3  # multiple distinct shapes

assert solution.numDistinctIslands([
    [0,0,0],
    [0,0,0]
]) == 0  # no islands

assert solution.numDistinctIslands([
    [1]
]) == 1  # single-cell island

assert solution.numDistinctIslands([
    [1,1],
    [1,1]
]) == 1  # one large square island

assert solution.numDistinctIslands([
    [1,0,1],
    [0,0,0],
    [1,0,1]
]) == 1  # multiple identical single-cell islands

assert solution.numDistinctIslands([
    [1,1,0],
    [0,1,0],
    [1,0,1]
]) == 3  # all islands different

assert solution.numDistinctIslands([
    [1,1,0,0],
    [1,0,0,0],
    [0,0,1,1],
    [0,0,0,1]
]) == 2  # mirrored shapes are distinct

assert solution.numDistinctIslands([
    [1,1,1],
    [1,0,1],
    [1,1,1]
]) == 1  # donut-shaped island
Test Why
Two identical square islands Validates translation equivalence
Multiple different island shapes Ensures distinct counting works
All water grid Validates zero-island handling
Single-cell grid Smallest possible island
One large island Ensures connected traversal works
Multiple isolated single cells Identical tiny islands counted once
Several structurally different islands Validates shape differentiation
Mirrored shapes Confirms reflections are treated as different
Complex connected island Tests traversal correctness on irregular structures

Edge Cases

One important edge case is a grid containing no land at all. A naive implementation might incorrectly initialize the answer to 1 or attempt DFS on water cells. The current implementation safely skips all water cells and leaves the distinct shape set empty, resulting in the correct answer of 0.

Another subtle edge case involves islands with the same number of cells but different structures. For example, an L-shaped island and a straight-line island may both contain three cells. Counting only island size would produce an incorrect result. The implementation avoids this bug by storing the exact relative coordinate structure of every island.

A third important edge case occurs when islands are mirrored or rotated versions of one another. Since the problem allows only translation, these should be considered distinct. Because the algorithm preserves the exact relative coordinates without normalization through rotation or reflection, mirrored islands naturally produce different signatures and are counted separately.

A final edge case involves very large connected islands. Recursive DFS could potentially revisit cells repeatedly if visitation tracking is implemented incorrectly. The solution prevents this by marking cells as visited immediately upon entering DFS, guaranteeing that every land cell is processed exactly once.