Skip to main content

21. Number of Islands

easyAsked at Doordash

Count connected land zones in a grid — Doordash uses this BFS/DFS classic to see if you can reason about delivery coverage zones and autonomous map-segmentation logic under time pressure.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n 2D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and is formed by connecting adjacent land cells horizontally or vertically.

Constraints

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

Examples

Example 1

Input
grid = [["1","1","1","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output
3

Explanation: Three separate connected land components exist.

Example 2

Input
grid = [["1","1"],["1","1"]]
Output
1

Approaches

1. Brute force DFS with visited set

Iterate all cells; on each unvisited land cell, DFS the full component, storing visited state in a separate Set.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  const visited = new Set();
  let count = 0;
  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n) return;
    const key = r * n + c;
    if (visited.has(key) || grid[r][c] === '0') return;
    visited.add(key);
    dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (!visited.has(r*n+c) && grid[r][c] === '1') {
        dfs(r, c);
        count++;
      }
    }
  }
  return count;
}

Tradeoff:

2. In-place BFS (mark visited by mutation)

BFS from each unvisited '1', immediately marking cells '0' to avoid a visited set. Optimal space — no extra data structure beyond the queue.

Time
O(m*n)
Space
O(min(m,n)) for BFS queue
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        count++;
        const queue = [[r, c]];
        grid[r][c] = '0';
        while (queue.length) {
          const [cr, cc] = queue.shift();
          for (const [dr, dc] of dirs) {
            const nr = cr + dr, nc = cc + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === '1') {
              grid[nr][nc] = '0';
              queue.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

Doordash-specific tips

Doordash interviewers often frame this as 'given a map grid of serviceable zones, count distinct delivery regions.' They want to hear you call out BFS vs DFS tradeoffs (BFS avoids stack overflow on large grids) and discuss how you'd extend this to weighted adjacency for drive-time zones. Mentioning the in-place mutation trick scores bonus points — it shows you think about memory in latency-sensitive services.

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 Doordash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →