Number of Islands

Approach Summary

DFS/BFS from each unvisited land cell, marking all connected land as visited. Count how many times you start a DFS.

Full Solution & Approach

An island is a connected group of 1s. Flood-fill each island with BFS: scan the grid, and every time you hit an unvisited 1 you have found a new island, so increment the count and flood-fill from that cell — visiting all four-directional neighbors and turning each visited 1 into 0 so it is never counted again. The flood fill can be BFS (queue) or DFS (recursion or stack); BFS is preferred to avoid deep recursion on large grids. Each cell is enqueued at most once, so the total work is O(m × n). Marking cells as visited by mutating the grid (1 → 0) avoids allocating a separate visited array and is the standard interview approach. The outer scan naturally skips water and already-visited land.

Every cell is processed at most once across all BFS calls — O(m × n) time. The BFS queue holds at most the frontier of a single island — O(min(m, n)) worst case, with no visited array because the grid is mutated in place.

Solution Code

Solution

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    count = 0

    def bfs(r: int, c: int) -> None:
        queue = [(r, c)]
        grid[r][c] = '0'
        for x, y in queue:
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                    grid[nx][ny] = '0'
                    queue.append((nx, ny))

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                count += 1
                bfs(r, c)
    return count

function numIslands(grid) {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0].length;
  let count = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        count++;
        const stack = [[r, c]];
        grid[r][c] = '0';
        while (stack.length) {
          const [x, y] = stack.pop();
          for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === '1') {
              grid[nx][ny] = '0';
              stack.push([nx, ny]);
            }
          }
        }
      }
    }
  }
  return count;
}

public int numIslands(char[][] grid) {
    if (grid.length == 0) return 0;
    int m = grid.length, n = grid[0].length;
    int count = 0;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == '1') {
                count++;
                Deque<int[]> queue = new ArrayDeque<>();
                queue.offer(new int[]{r, c});
                grid[r][c] = '0';
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    for (int[] d : dirs) {
                        int nr = cell[0] + d[0], nc = cell[1] + d[1];
                        if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
                            grid[nr][nc] = '0';
                            queue.offer(new int[]{nr, nc});
                        }
                    }
                }
            }
        }
    }
    return count;
}

int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    int count = 0;
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == '1') {
                count++;
                queue<pair<int,int>> q;
                q.push({r, c});
                grid[r][c] = '0';
                while (!q.empty()) {
                    auto [x, y] = q.front(); q.pop();
                    for (auto& d : dirs) {
                        int nr = x + d[0], nc = y + d[1];
                        if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
                            grid[nr][nc] = '0';
                            q.push({nr, nc});
                        }
                    }
                }
            }
        }
    }
    return count;
}

Edge Cases to Watch

Empty grid — return 0
Single-cell grid
Grid where all land is connected — count is 1
Grid with only water — count is 0
Land that touches only diagonally — NOT connected; use 4-directional neighbors only

How to Recognize This Pattern

Count connected components in grid
Flood fill

Complexity Analysis

Time Complexity

O(m × n)

Space Complexity