Skip to main content

21. Number of Islands

mediumAsked at Box

Count connected regions in a binary grid — Box uses a structurally identical algorithm to discover isolated file clusters and orphaned permission groups inside enterprise collaboration networks.

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. Brute force — BFS with visited set

For each unvisited land cell, run BFS to mark all connected land cells as visited using a separate boolean grid.

Time
O(m * n)
Space
O(m * n)
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  const visited = Array.from({length: m}, () => Array(n).fill(false));
  let count = 0;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1' && !visited[r][c]) {
        count++;
        const queue = [[r, c]];
        visited[r][c] = true;
        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' && !visited[nr][nc]) {
              visited[nr][nc] = true;
              queue.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

2. Optimal — DFS in-place sink

Mutate the grid in place: when land is found, DFS-flood-fill it to '0' so it is never revisited. Eliminates the O(m*n) visited array.

Time
O(m * n)
Space
O(min(m,n)) 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'; // sink
    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:

Box-specific tips

Box values the in-place approach but will ask whether mutating the input is safe — a key real-world concern when the grid represents live permission data. Mention Union-Find as a third option if they ask about very large distributed grids, since Box's backend processes petabytes of file metadata across sharded storage nodes.

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

Practice these live with InterviewChamp.AI →