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.

Please do not post any spam link in the comment box😊

إرسال تعليق (0)
أحدث أقدم