Number of Islands in a Grid

medium graph dfs grid

Problem

A grid contains land cells (1) and water cells (0). Two land cells belong to the same island when they share an edge (no diagonals). Count how many distinct islands the grid contains.

Scan every cell. The first time you see an unvisited land cell, increment the island count and flood-fill the whole connected region with DFS so every other cell of that island is marked visited.

Input

Output5

grid (rows separated by ';', cells by space or comma)

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols:
            return
        if grid[r][c] != 1:
            return
        grid[r][c] = 2
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                count += 1
                dfs(r, c)
    return count

function countIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;
  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols) return;
    if (grid[r][c] !== 1) return;
    grid[r][c] = 2;
    dfs(r + 1, c); dfs(r - 1, c);
    dfs(r, c + 1); dfs(r, c - 1);
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === 1) { count++; dfs(r, c); }
  return count;
}

class Solution {
    int[][] g; int R, C;
    public int countIslands(int[][] grid) {
        g = grid; R = grid.length; C = grid[0].length;
        int count = 0;
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                if (g[r][c] == 1) { count++; dfs(r, c); }
        return count;
    }
    void dfs(int r, int c) {
        if (r < 0 || c < 0 || r >= R || c >= C) return;
        if (g[r][c] != 1) return;
        g[r][c] = 2;
        dfs(r + 1, c); dfs(r - 1, c);
        dfs(r, c + 1); dfs(r, c - 1);
    }
}

int R, C;
void dfs(vector<vector<int>>& g, int r, int c) {
    if (r < 0 || c < 0 || r >= R || c >= C) return;
    if (g[r][c] != 1) return;
    g[r][c] = 2;
    dfs(g, r + 1, c); dfs(g, r - 1, c);
    dfs(g, r, c + 1); dfs(g, r, c - 1);
}
int countIslands(vector<vector<int>> grid) {
    R = grid.size(); C = grid[0].size();
    int count = 0;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (grid[r][c] == 1) { count++; dfs(grid, r, c); }
    return count;
}

Time: O(R · C) Space: O(R · C) recursion worst case