Skip to main content

Number of Islands Pattern

The Number of Islands problem is a classic grid-based problem that involves finding the number of distinct islands in a 2D grid. An island is formed by connected groups of 1s (land), and they are surrounded by 0s (water). The land cells can be connected either vertically or horizontally, but not diagonally.

Problem Statement​

You are given a 2D grid of 1s (land) and 0s (water). Your task is to count the number of islands. An island is a group of 1s connected vertically or horizontally, and surrounded by water (0s).

Graph Traversal Pattern​

This problem uses a graph traversal pattern where you need to explore and mark connected components in a grid. This pattern can be applied to other problems such as finding the size of the largest connected component or counting distinct regions.

Algorithm​

  1. Graph Representation:

    • Treat the grid as a graph where each cell is a node.
    • Cells with value 1 are land and can be treated as connected if they are adjacent (up, down, left, right).

  2. DFS/BFS for Traversal:

    • Use DFS or BFS to explore the entire component (all connected land cells) starting from a 1. Once you visit a land cell, mark it as visited (by changing it to 0 or using a visited array).
    • For every unvisited land cell, initiate a new DFS/BFS traversal, and count it as a new island.

  3. Marking Visited:

    • Once you visit a cell, mark it as visited to avoid counting the same island multiple times. This can be done by:
      • Modifying the grid in-place (changing 1 to 0 after visiting).
      • Using a visited array to track visited cells.

DFS Approach​

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
function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;

    let numIslands = 0;
    const rows = grid.length;
    const cols = grid[0].length;

    // Helper function to perform DFS
    const dfs = (grid, r, c) => {
        // Base case: check bounds and if the current cell is water or already visited
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return;

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

        // Explore the neighboring cells (up, down, left, right)
        dfs(grid, r - 1, c); // up
        dfs(grid, r + 1, c); // down
        dfs(grid, r, c - 1); // left
        dfs(grid, r, c + 1); // right
    };

    // Iterate through the entire grid
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') {
                // Found an island, increment the count
                numIslands++;

                // Use DFS to mark all connected land as visited
                dfs(grid, r, c);
            }
        }
    }

    return numIslands;
}