General

No Comments

Counting the Number of Islands in a Grid

The “Number of Islands” problem is a classic question often asked in coding interviews. It tests your understanding of depth-first search (DFS) and breadth-first search (BFS) algorithms and your ability to work with 2D arrays. In this article, we will explore different approaches to solving this problem using JavaScript.

Problem Statement

Given a 2D grid consisting of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Example

Input:

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

Output: 3

Approach 1: Depth-First Search (DFS)

The DFS algorithm is a natural choice for this problem. We can use it to explore all parts of an island and mark them as visited.

Steps

  1. Initialize a counter for islands.
  2. Iterate through each cell in the grid.
  3. When a ‘1’ is found, increase the island counter and perform a DFS to mark all adjacent lands as visited.
  4. Continue until all cells are processed.
function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;
  
  let count = 0;
  
  const dfs = (grid, i, j) => {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] === '0') {
      return;
    }
    
    grid[i][j] = '0'; // Mark the cell as visited
    
    dfs(grid, i + 1, j); // Down
    dfs(grid, i - 1, j); // Up
    dfs(grid, i, j + 1); // Right
    dfs(grid, i, j - 1); // Left
  };
  
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j] === '1') {
        count++;
        dfs(grid, i, j);
      }
    }
  }
  
  return count;
}

// Test the function
const grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
];

console.log(numIslands(grid)); // Output: 3

Explanation

  1. We define the dfs function to recursively mark all connected lands (‘1’) as visited by turning them into ‘0’.
  2. We iterate through each cell of the grid. When we find a ‘1’, we increase the island count and call dfs to mark the entire island as visited.

Approach 2: Breadth-First Search (BFS)

The BFS algorithm can also be used to solve this problem. Instead of recursion, BFS uses a queue to explore all parts of an island.

Steps

  1. Initialize a counter for islands.
  2. Iterate through each cell in the grid.
  3. When a ‘1’ is found, increase the island counter and perform a BFS to mark all adjacent lands as visited.
  4. Continue until all cells are processed.
function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;
  
  let count = 0;
  
  const bfs = (grid, i, j) => {
    const queue = [];
    queue.push([i, j]);
    grid[i][j] = '0';
    
    while (queue.length > 0) {
      const [x, y] = queue.shift();
      
      const directions = [
        [x + 1, y], // Down
        [x - 1, y], // Up
        [x, y + 1], // Right
        [x, y - 1]  // Left
      ];
      
      for (const [newX, newY] of directions) {
        if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] === '1') {
          queue.push([newX, newY]);
          grid[newX][newY] = '0';
        }
      }
    }
  };
  
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j] === '1') {
        count++;
        bfs(grid, i, j);
      }
    }
  }
  
  return count;
}

// Test the function
const grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
];

console.log(numIslands(grid)); // Output: 3

Explanation

  1. We define the bfs function to iteratively mark all connected lands (‘1’) as visited by turning them into ‘0’.
  2. We iterate through each cell of the grid. When we find a ‘1’, we increase the island count and call bfs to mark the entire island as visited
Close Menu