Skip to main content

19. Number of Islands

mediumAsked at CircleCI

Count connected land components in a grid, an abstraction CircleCI uses to reason about isolated sub-graphs within a larger pipeline dependency network.

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

Problem

Given an m x n grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. DFS flood-fill

Iterate cells; on finding '1', run DFS to mark the whole island as visited.

Time
O(m*n)
Space
O(m*n)
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') { dfs(r, c); count++; }
  return count;
}

Tradeoff:

2. Union-Find

Use a disjoint-set structure to union adjacent land cells; the number of distinct roots equals island count. Scales well for streaming/online updates to the grid.

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;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (grid[i][j] === '1') count++;
  function find(x) { return parent[x] === x ? x : parent[x] = find(parent[x]); }
  function union(a, b) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) { parent[ra] = rb; count--; }
  }
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (grid[i][j] === '1')
        for (const [dr, dc] of dirs) {
          const ni = i+dr, nj = j+dc;
          if (ni>=0 && ni<m && nj>=0 && nj<n && grid[ni][nj]==='1')
            union(i*n+j, ni*n+nj);
        }
  return count;
}

Tradeoff:

CircleCI-specific tips

CircleCI interviewers may frame this as detecting isolated job clusters — mention Union-Find's advantage for incremental pipeline updates where new edges are added at runtime.

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

Practice these live with InterviewChamp.AI →