Number of Islands

medium graph dfs grid

Problem

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.

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 num_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 numIslands(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 numIslands(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 numIslands(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;
}

Explanation

An island is a clump of land cells (1s) joined up, down, left or right. We want to count how many separate clumps there are.

We scan the grid cell by cell. Most cells are water or already-counted land, so we skip them. The interesting moment is finding a fresh, unvisited land cell — that means we just bumped into a brand-new island, so we add 1 to the count.

To make sure we do not count the same island again, we then flood-fill it: starting from that cell, we visit every connected land cell and mark it as seen (the code flips 1 to 2). This is a depth-first search that spreads out in all four directions.

By the time the scan finishes, every island has been discovered exactly once at its first cell and then fully erased, so the count is correct.

Think of it like spilling water on a piece of land: one starting drop spreads to cover the whole connected patch.

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