Number of Islands - BFS

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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 all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

---

1) Explain the problem

The problem is to find the number of islands in a given 2D binary grid where '1' represents land and '0' represents water. An island is formed by connecting adjacent lands horizontally or vertically. The goal is to count how many separate islands exist in the grid.

2) Short easy to remember solution/approach

• Use Depth-First Search (DFS) to explore each land cell ('1') and mark all connected land cells as visited by changing their value to '0'.

• Iterate through the grid, and for each unvisited land cell, initiate a DFS to mark the entire island and increment the island count.

3) Solution in JavaScript with code commenting

function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;

    let count = 0;

    const dfs = (r, c) => {
        // If the cell is out of bounds or is water, return
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] === '0') {
            return;
        }

        // Mark the cell as visited by changing it to '0'
        grid[r][c] = '0';

        // Recursively visit all adjacent cells (up, down, left, right)
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    };

    // Iterate through all cells in the grid
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            // If we find an unvisited land cell, start a DFS to mark the island
            if (grid[i][j] === '1') {
                count++;
                dfs(i, j);
            }
        }
    }

    return count;
}

4) Explanation of the solution in an easy-to-understand way with a real-life example

Imagine you are in a large field with patches of grass (land) and dirt (water). You want to count how many separate patches of grass there are. You start walking from one patch of grass, mark it as visited, and then move to the adjacent patches, marking them all as visited until there are no more connected patches. You repeat this process for any unvisited patches you encounter and count each time you start a new patch. This is how the algorithm works to count islands.

5) Code explanation in pointers

• Initialize: Check if the grid is empty; if so, return 0 islands.

• Count Initialization: Initialize a counter to keep track of the number of islands.

• DFS Function:

  • Boundary Check: Ensure the cell is within bounds and is land ('1').

  • Mark Visited: Change the cell value to '0' to mark it as visited.

  • Recursion: Recursively call the function for all four adjacent cells (up, down, left, right).

• Grid Iteration:

  • Unvisited Land Check: For each cell, if it's an unvisited land ('1'), increment the island count and initiate DFS from that cell.

• Return Count: Return the total number of islands counted.

6) Complexities

• Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid. In the worst case, every cell may be visited once.

• Space Complexity: O(m * n) for the call stack in the worst case due to recursion.