12. Number of Islands

mediumAsked at GitHub

BFS/DFS grid traversal that mirrors how GitHub models repository dependency graphs and connected component analysis.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Given an m×n 2D binary grid of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Constraints

1 <= m, n <= 300
grid[i][j] is '0' or '1'

Examples

Example 1

Input

grid = [['1','1','0'],['1','1','0'],['0','0','1']]

Output

Example 2

Input

grid = [['1','0','1'],['0','1','0'],['1','0','1']]

Output

Approaches

1. Brute force DFS with visited matrix

Track visited cells in a separate boolean matrix while iterating the grid.

Time: O(m*n)
Space: O(m*n)

const visited = Array.from({length: m}, () => new Array(n).fill(false));
// DFS on each unvisited '1', mark all connected cells visited
// increment count for each DFS root

Tradeoff:

2. BFS with in-place marking

Mark visited land cells as '0' in-place during BFS to avoid extra space. For each unvisited '1', enqueue it, mark as '0', and flood-fill neighbors.

Time: O(m*n)
Space: O(min(m,n))

function numIslands(grid) {
  let count = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === '1') {
        count++;
        const queue = [[i, j]];
        grid[i][j] = '0';
        while (queue.length) {
          const [r, c] = queue.shift();
          for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] === '1') {
              grid[nr][nc] = '0';
              queue.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

GitHub-specific tips

GitHub interviews favor BFS for graph/grid problems because it maps directly to commit-graph traversal; mention how the same pattern applies to resolving transitive dependencies in a package graph.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Number of Islands and other GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →