Number of Distinct Islands
Using DFS Shape Encoding

⬅ Previous Topic

Word Ladder II - All Shortest Transformation Sequences

Next Topic ⮕

Topic Contents

Problem Examples Solution Algorithm Code Time Space

Problem Statement

Given a 2D grid of size N x M consisting of '1's (land) and '0's (water), your task is to find the number of distinct islands. An island is a group of connected '1's (land) in 4 directions (horizontal and vertical). Two islands are considered distinct if and only if their shape (relative position of land cells) is different.

Examples❯

Grid	Distinct Islands	Description
[[1,1,0,0],[1,0,0,0],[0,0,1,1],[0,0,0,1]]	2	Two unique island shapes
[[1,1,0],[1,1,0],[0,0,0]]	1	Only one island shape
[[0,0],[0,0]]	0	No land present
[[1]]	1	Single land cell
[[1,0,1],[0,0,0],[1,0,1]]	4	Each land cell is isolated and unique

Solution❯

Understanding the Grid

We're given a grid of 0s and 1s, where '1' represents land and '0' represents water. Our task is to identify and count how many distinct island shapes exist. An island is a group of connected 1s (land) connected either vertically or horizontally.

What Makes an Island Distinct?

Two islands are considered the same if their shapes are identical after translating them to the same origin (no rotation or flipping allowed). To capture the shape of each island, we use a technique called DFS Shape Encoding.

DFS and Shape Encoding

When we find a land cell that hasn't been visited, we initiate a DFS. As we move from cell to cell, we record the direction we move (e.g., 'U' for up, 'D' for down, 'L' for left, 'R' for right). This directional path becomes a unique signature for the island.

To ensure each island shape is encoded consistently, we also record a 'B' (backtrack) symbol each time we return from a recursive DFS call. This prevents shapes like a square and a zig-zag with the same number of cells from being confused.

Edge Cases

Empty Grid: The output will be 0 because there are no islands.
All Water: Still 0, as there are no land cells.
All Land: Output is 1, since the whole grid is a single large island.
Different but Same-Sized Islands: If two islands have different shapes (even if they have the same number of cells), they are considered distinct and counted separately.

Result

At the end, we return the number of unique strings in the shapes set — each string representing a unique island shape.

Algorithm Steps

Initialize an empty set shapes to store unique island signatures.
Iterate through each cell in the grid.
When a land cell ('1') is found that is not visited:

Start a DFS from that cell, marking visited cells.
Track the shape of the island by recording moves relative to the start cell.
Store the shape string in the shapes set.

Return the number of elements in shapes.

Code

JavaScript

function numDistinctIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
  const shapes = new Set();

  const directions = [
    [0, 1, 'R'], // right
    [0, -1, 'L'], // left
    [1, 0, 'D'], // down
    [-1, 0, 'U'] // up
  ];

  function dfs(r, c, path, dir) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c] || grid[r][c] === 0) return;
    visited[r][c] = true;
    path.push(dir);
    for (const [dr, dc, d] of directions) {
      dfs(r + dr, c + dc, path, d);
    }
    path.push('B'); // Backtrack
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1 && !visited[r][c]) {
        const path = [];
        dfs(r, c, path, 'S'); // Start
        shapes.add(path.join(''));
      }
    }
  }

  return shapes.size;
}

// Example Usage
console.log("Distinct Islands:", numDistinctIslands([
  [1,1,0,0],
  [1,0,0,0],
  [0,0,1,1],
  [0,0,0,1]
])); // Output: 2

Time Complexity

Case	Time Complexity	Explanation
Best Case	O(m * n)	Even in the best case, we must visit every cell to check if it's land or water and track unique shapes.
Average Case	O(m * n)	Each cell is visited once, and DFS explores each connected component, tracking the shape.
Worst Case	O(m * n)	In the worst case (e.g., entire grid is land), DFS explores all cells, and all must be encoded and compared.

Space Complexity

O(m * n)

Explanation: In the worst case, all cells are part of different islands, requiring separate shape strings and a visited matrix of the same size.

⬅ Previous Topic

Word Ladder II - All Shortest Transformation Sequences

Next Topic ⮕

Check if a Graph is Bipartite using DFS

Overview of Techniques14
❯

Sorting6
❯

Arrays32
❯

Arrays - Binary Search28
❯

Strings18
❯

Matrix3
❯

Matrix - Binary Search5
❯

Binary Trees36
❯

Binary Search Trees14
❯

Graphs46
❯

Tries1
❯

Number of Distinct Islands
Using DFS Shape Encoding

Problem Statement

Examples❯

Solution❯

Understanding the Grid

What Makes an Island Distinct?

DFS and Shape Encoding

Edge Cases

Result

Algorithm Steps

Code

Time Complexity

Space Complexity

Support ProgramGuru.org❯

Number of Distinct IslandsUsing DFS Shape Encoding

Problem Statement

Examples❯

Solution❯

Understanding the Grid

What Makes an Island Distinct?

DFS and Shape Encoding

Edge Cases

Result

Algorithm Steps

Code

Time Complexity

Space Complexity

Welcome to ProgramGuru

Support ProgramGuru.org❯

Number of Distinct Islands
Using DFS Shape Encoding