Skip to main content

22. Number of Islands

mediumAsked at Coinbase

Count disconnected clusters in a grid — Coinbase maps this to partitioning liquidity pools or detecting isolated market segments that cannot route to a shared settlement layer.

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","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 unvisited '1' cell, run DFS to mark the whole island as visited, increment counter.

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

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

Tradeoff:

2. BFS flood-fill (iterative)

Same idea with a queue instead of recursion — avoids stack overflow on large grids.

Time
O(m * n)
Space
O(min(m, n)) BFS queue
function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue;
      count++;
      grid[r][c] = '0';
      const queue = [[r, c]];
      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 < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

Coinbase-specific tips

Coinbase frames this as a connectivity problem: given a graph of liquidity providers, how many isolated clusters exist that cannot route a trade to the central book? They want you to note the in-place mutation tradeoff — it is faster but destroys input, which matters in a trading system with immutable market-state snapshots. Mentioning Union-Find as a third approach signals senior-level graph fluency.

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

Practice these live with InterviewChamp.AI →