Skip to main content

10. Number of Islands

mediumAsked at Confluent

Count connected components of '1' cells in a grid — Confluent uses it because the BFS/DFS flood is the same shape as discovering live partitions across a Kafka cluster.

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

Problem

Given an m x n grid of '1' (land) and '0' (water), return the number of islands. An island is a maximal group of 4-directionally connected land cells, with all edges padded by water.

Constraints

  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'

Examples

Example 1

Input
grid=[['1','1','0'],['1','0','0'],['0','0','1']]
Output
2

Example 2

Input
grid=[['1','1','1'],['0','1','0'],['1','1','1']]
Output
1

Approaches

1. Union-Find

Union adjacent land cells; the final root count of land cells is the answer.

Time
O(mn * alpha)
Space
O(mn)
// parent[], rank[]; iterate cells; union right and down neighbors if both '1'

Tradeoff:

2. DFS flood fill

Scan the grid; on each unvisited '1' increment the count and DFS-flood, marking visited land as '0' to avoid re-counting.

Time
O(mn)
Space
O(mn)
function numIslands(grid) {
  let count = 0;
  const m = grid.length, n = grid[0].length;
  function dfs(i, j) {
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] !== '1') return;
    grid[i][j] = '0';
    dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1);
  }
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (grid[i][j] === '1') { count++; dfs(i, j); }
  return count;
}

Tradeoff:

Confluent-specific tips

Confluent will pivot to a distributed variant — describe how each partition could BFS locally and then merge boundary cells via a coordinator, mirroring partition assignment across consumer-group members.

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

Practice these live with InterviewChamp.AI →