Counting the Number of Islands in a 2D Grid: An Efficient Depth-First Search

Islands in a grid are formed by connecting adjacent land cells (L). We are tasked with finding the smallest island in a given grid. In this blog post, we’ll explore how to approach this problem using depth-first search (DFS), breaking it down step-by-step. 

Problem Definition

We have a grid represented by a 2D array where:

• W represents water.
• L represents land.

An island is a group of connected land cells (L). Connected means horizontal or vertical adjacency, not diagonal. We need to find the minimum island size in the grid.

Here’s the grid:

const grid = 
 [  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'W', 'W', 'L', 'W'],
  ['W', 'W', 'L', 'L', 'W'],
  ['L', 'W', 'W', 'L', 'L'],
  ['L', 'L', 'W', 'W', 'W'],
];

Approach

To solve this, we can use DFS to explore all land cells (L) connected to a starting cell. We’ll iterate over each cell in the grid, and if it’s part of an island that hasn’t been visited yet, we will perform a DFS to calculate the size of that island. The minimum size encountered during this process will be our result.

Steps

1. Mark Cells as Visited: As we traverse the grid, we need to track the cells we’ve already visited to avoid recounting the same island.
2. Depth-First Search (DFS): We’ll use DFS to explore all the adjacent cells that are part of the same island.
3. Track Minimum Island Size: After exploring each island, update the minimum size if the current island is smaller than the previously recorded minimum.

Here’s the DFS-based solution:

const minimumIsland = (grid) => {
  const visited = new Set();
  let minSize = Infinity;

  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      const size = exploreIsland(grid, r, c, visited);
      if (size > 0 && size < minSize) {
        minSize = size;
      }
    }
  }

  return minSize;
};

const exploreIsland = (grid, r, c, visited) => {
  const rowInBounds = r >= 0 && r < grid.length;
  const colInBounds = c >= 0 && c < grid[0].length;
  if (!rowInBounds || !colInBounds || grid[r][c] === 'W') return 0;

  const pos = r + ',' + c;
  if (visited.has(pos)) return 0;
  
  visited.add(pos);

  let size = 1; // count the current land
  size += exploreIsland(grid, r - 1, c, visited); // up
  size += exploreIsland(grid, r + 1, c, visited); // down
  size += exploreIsland(grid, r, c - 1, visited); // left
  size += exploreIsland(grid, r, c + 1, visited); // right

  return size;
};

console.log(minimumIsland(grid)); // -> 2

DFS Explained

• We start from a cell, check if it’s a land cell (L), and if so, mark it as visited.
• We recursively explore its neighbors (up, down, left, right).
• As we explore, we count the number of land cells connected to form the current island.
• Once all connected cells have been visited, we compare the size of the island with the current minimum size and update if needed.