Skip to main content

19. Number of Islands

mediumAsked at GitLab

Count connected components of '1' cells in a 2D grid where neighbors are 4-directional.

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

Problem

Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is a maximal group of land cells connected horizontally or vertically.

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=[['0','0'],['0','0']]
Output
0

Approaches

1. Union-find on cells

Union every land cell with its right/down neighbor; count distinct roots over land cells.

Time
O(m*n*alpha)
Space
O(m*n)
/* DSU with rank + path compression over m*n cells, union 4-direction land neighbors, then dedup roots. */

Tradeoff:

2. DFS flood-fill

Scan the grid; on each unvisited '1', DFS the component and sink it to '0', incrementing the island counter once per launch.

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

Tradeoff:

GitLab-specific tips

GitLab frames islands as 'connected MR review clusters' — they want you to reason about how you'd parallelize the flood-fill across a runner pool when the grid is sharded.

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

Practice these live with InterviewChamp.AI →