Skip to main content

17. Number of Islands

mediumAsked at Chime

Count the number of connected land regions in a 2D grid of land and water cells.

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 a group of land cells connected horizontally or vertically; the grid edges are assumed to be water.

Constraints

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

Examples

Example 1

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

Example 2

Input
[['1','0','1','0','1']]
Output
3

Approaches

1. Union-find on every cell

Treat every land cell as a node and union adjacent land neighbors; count distinct roots at the end.

Time
O(m*n * alpha(m*n))
Space
O(m*n)
// Build parent[] over m*n cells
// For each land cell, union with neighbors on right and below
// Count distinct roots whose cell is land

Tradeoff:

2. DFS flood fill

Scan the grid; on each unvisited land cell, increment the counter and flood-fill its connected region in place by marking visited.

Time
O(m*n)
Space
O(m*n)
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:

Chime-specific tips

Chime maps this onto clusters of fraud heuristics signals sharing a device fingerprint, so highlight how the same flood-fill counts coordinated bad actors.

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

Practice these live with InterviewChamp.AI →