Skip to main content

26. Number of Islands

mediumAsked at Lyft

Count connected land regions in a grid — Lyft uses the same BFS flood-fill to identify distinct geographic service zones from binary availability grids when partitioning its coverage map into driver dispatch regions.

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

Problem

Given an m x n 2D binary 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. You may assume all four edges of the grid are surrounded by water.

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","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Output
1

Example 2

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

Approaches

1. DFS flood-fill

Iterate every cell. When a '1' is found, increment count and DFS to sink (mark '0') all connected land. DFS recurses in 4 directions.

Time
O(m * n)
Space
O(m * n) recursion stack
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === '0') return;
    grid[r][c] = '0';
    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 (grid[r][c] === '1') { count++; dfs(r, c); }
    }
  }
  return count;
}

Tradeoff:

2. BFS flood-fill

Same island-counting loop, but flood-fill with an explicit queue instead of recursion. Avoids stack overflow on large grids — preferred for production-scale m * n = 300 * 300.

Time
O(m * n)
Space
O(min(m, n)) queue at max BFS frontier
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') continue;
      count++;
      const queue = [[r, c]];
      grid[r][c] = '0';
      while (queue.length) {
        const [row, col] = queue.shift();
        for (const [dr, dc] of dirs) {
          const nr = row + dr, nc = col + 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:

Lyft-specific tips

Lyft often extends this problem: 'What if the grid is too large to fit in memory — can you handle it as a stream of rows?' Be ready to discuss Union-Find for dynamic island merging as new cells arrive. For the interview itself, BFS is preferred over recursive DFS because it avoids stack overflows on the 300x300 constraint — mention that explicitly.

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

Practice these live with InterviewChamp.AI →