Skip to main content

15. Number of Islands

easyAsked at Quora

Count connected components in a binary grid — at Quora this translates directly to identifying isolated topic clusters in the user-question graph, a real signal in their content-quality pipeline.

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

Problem

Given an m x n 2D binary grid of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically. You may assume all four edges are surrounded by water.

Constraints

  • 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

Scan each cell; on finding an unvisited '1', increment count and DFS to mark the whole island as visited by sinking to '0'.

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

Tradeoff:

2. Union-Find (disjoint sets)

Initialise each '1' as its own component; union adjacent '1' cells. Answer is the final component count. Preferred when the grid can't be mutated.

Time
O(m * n * alpha(m*n))
Space
O(m * n)
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  const parent = Array.from({ length: m * n }, (_, i) => i);
  let count = 0;
  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }
  function union(a, b) {
    const pa = find(a), pb = find(b);
    if (pa !== pb) { parent[pa] = pb; count--; }
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        count++;
        if (r + 1 < m && grid[r + 1][c] === '1') union(r * n + c, (r + 1) * n + c);
        if (c + 1 < n && grid[r][c + 1] === '1') union(r * n + c, r * n + c + 1);
      }
    }
  }
  return count;
}

Tradeoff:

Quora-specific tips

Quora grades both solutions but specifically probes the Union-Find variant to see if you can reason about dynamic merges — the same structure underlies how they merge duplicate-question clusters at scale.

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

Practice these live with InterviewChamp.AI →