Number of Islands

Why it belongs on this sheet

This is one of the most common graph and grid traversal problems in interview prep.

Pattern

Connected component counting

Approach

Scan the grid. Whenever you find unvisited land, increment the island count and run DFS to mark that whole component as visited.

Java solution

class Solution {
  public int numIslands(char[][] grid) {
    int islands = 0;

    for (int row = 0; row < grid.length; row++) {
      for (int col = 0; col < grid[0].length; col++) {
        if (grid[row][col] == '1') {
          islands++;
          sink(grid, row, col);
        }
      }
    }

    return islands;
  }

  private void sink(char[][] grid, int row, int col) {
    if (
      row < 0 || col < 0 || row == grid.length || col == grid[0].length
      || grid[row][col] != '1'
    ) {
      return;
    }

    grid[row][col] = '0';
    sink(grid, row + 1, col);
    sink(grid, row - 1, col);
    sink(grid, row, col + 1);
    sink(grid, row, col - 1);
  }
}

Complexity

• Time: O(m * n)
• Space: O(m * n) in the worst recursive case

Interview note

You can say "each land cell is visited once" as the main time-complexity argument.