Number of Distinct Islands Using DFS Shape Encoding

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]]	1	Even though there are four islands, all the four islands have same shape. Therefore, number of uniquely shaped islands is 1.
[[1,1,0,0],[1,0,0,1],[0,0,1,1],[0,1,0,0]]	3	Three distinct island shapes: L-shape, vertical, and single
[[1,1,0,0],[1,0,0,1],[0,0,0,1],[1,1,1,0],[1,0,0,0]]	3	Three island shapes: top-left block, vertical line, and bottom L-shape

Visualization Player

Solution❯

Understanding the Problem

We are given a 2D grid consisting of 0s and 1s. Here, '1' represents land, and '0' represents water. An island is a group of connected 1s in the grid, where connections are allowed only in four directions—up, down, left, and right.

Our goal is to count how many distinct island shapes exist. Two islands are considered the same if they have the same shape when shifted to the same origin. That means rotation and flipping do not count; only translation (shifting) is allowed when comparing shapes.

Step-by-Step Solution with Example

step 1: Traverse the grid to find unvisited land cells

We start scanning the grid from the top-left corner. When we encounter a cell with value 1 that hasn't been visited yet, it means we've found the start of a new island.

step 2: Perform DFS to explore the full island

From the current cell, we perform a Depth-First Search (DFS) in all four directions. For each direction we move, we add a corresponding character to a path string to encode the shape. For example, 'U' for up, 'D' for down, 'L' for left, 'R' for right.

step 3: Add backtracking information to avoid false matches

Every time we finish a recursive DFS call and go back to the previous cell, we add a special symbol, such as 'B' for backtrack. This helps us capture the exact structure of the island. For instance, a line and a zig-zag of the same length would produce different signatures.

step 4: Store the encoded shape in a set

Once the DFS is complete for an island, we add the shape signature to a set. This ensures we only keep unique shapes.

step 5: Count the number of unique shapes

At the end of the traversal, the number of distinct islands is simply the size of the set that stores the shape signatures.

Example


Input:
[
  [1,1,0,0,0],
  [1,0,0,0,0],
  [0,0,0,1,1],
  [0,0,0,1,1]
]

We find two islands:
- The first one on the top-left forms a shape with path: "DRB"
- The second one on the bottom-right has the same shape: "DRB"

Even though they are in different locations, their shapes are the same, so the output is: 1

Edge Cases

Empty Grid: If the grid is empty, we return 0 since there are no islands.
All Water: If every cell is 0, there’s no land to explore. Output is 0.
All Land: If every cell is 1, there’s one big island. So, output is 1.
Same Size but Different Shapes: If two islands have the same number of cells but different layouts, they are still considered distinct.
Multiple Identical Shapes: If multiple islands have the same shape, they’re only counted once because we use a set to store unique patterns.

Finally

This problem helps build a strong foundation in graph traversal and pattern recognition. The key idea is not just visiting islands, but encoding their traversal paths uniquely to compare their shapes. Using DFS with shape encoding and backtracking gives us a reliable way to distinguish islands by structure.

Always consider boundary conditions and edge cases before finalizing your solution. Sets are a powerful way to track distinct patterns without worrying about duplicates.

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 TopicWord Ladder II - All Shortest Transformation Sequences

Next Topic ⮕Check if a Graph is Bipartite using DFS

Comments

Loading comments...