Skip to main content

18. Number of Islands

mediumAsked at Dropbox

Count distinct connected regions in a binary grid — Dropbox draws on this pattern when resolving which file clusters have been independently modified across disconnected clients during a conflict sweep.

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

Problem

Given a 2D binary grid 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 land cells 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

Explanation: All connected '1's form a single island.

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 with in-place marking

Iterate every cell; when a '1' is found, flood-fill via DFS, marking visited cells '0'. Increment the island count per DFS invocation.

Time
O(m*n)
Space
O(m*n) recursion stack
function numIslands(grid) {
  let count = 0;
  function dfs(r, c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] !== '1') 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 < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff:

2. BFS iterative

Same flood-fill logic but with an explicit queue, avoiding deep recursion that can overflow on large grids.

Time
O(m*n)
Space
O(min(m,n)) queue
function numIslands(grid) {
  let count = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; 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;
          const nc = col + 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:

Dropbox-specific tips

Dropbox typically frames this as a connectivity question about file clusters rather than a grid. Be ready to discuss Union-Find as a third approach — it's the structure Dropbox's distributed sync layer actually resembles, and naming it shows systems awareness.

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

Practice these live with InterviewChamp.AI →