Skip to main content

22. Number of Islands

mediumAsked at Etsy

Count connected components in a grid — Etsy uses this BFS/DFS graph pattern to cluster seller locations into regional fulfillment zones.

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

For each cell with value '1', increment island count and DFS to mark the entire connected component as visited by setting cells to '0'. Avoids a separate visited set by mutating the grid.

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] !== '1') return;
    grid[r][c] = '0'; // mark visited
    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 logic but uses an explicit queue rather than recursion, avoiding stack-overflow on very large grids. Enqueue each '1' cell, mark immediately on enqueue, then expand neighbors.

Time
O(m * n)
Space
O(min(m, n)) — 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') continue;
      count++;
      grid[r][c] = '0';
      const queue = [[r, c]];
      let head = 0;
      while (head < queue.length) {
        const [row, col] = queue[head++];
        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:

Etsy-specific tips

Etsy's logistics team uses connected-component analysis for clustering seller warehouses. When you mutate the grid, mention it as a deliberate tradeoff — if the input is read-only, you'd maintain a separate visited Set with composite keys. Interviewers also ask for the Union-Find variant to check if you know a third approach.

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

Practice these live with InterviewChamp.AI →