21. Number of Islands

mediumAsked at Mercury

Count the number of disjoint islands of '1's in a 2D grid.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Given an m x n grid of '1' (land) and '0' (water), return the number of islands. An island is a maximal set of land cells connected 4-directionally; the grid border counts as water.

Constraints

1 <= m, n <= 300
grid[i][j] in {'0','1'}

Examples

Example 1

Input

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

Output

Example 2

Input

grid = [['0']]

Output

Approaches

1. Union-Find over cells

Union each land cell with its right/down neighbor if land; count roots.

Time: O(mn alpha(mn))
Space: O(mn)

// build parent[] sized m*n, union neighbors when both '1', then count distinct roots among land cells.

Tradeoff:

2. DFS flood fill

Scan the grid; on each unvisited land cell, increment count and DFS-mark every reachable land cell to water. Linear in cells.

Time: O(m*n)
Space: O(m*n)

function numIslands(grid) {
  let count = 0;
  const dfs = (r, c) => {
    if (r < 0 || c < 0 || r >= grid.length || 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') { count++; dfs(r, c); }
    }
  }
  return count;
}

Tradeoff:

Mercury-specific tips

Mercury maps connected-components onto entity-resolution KYC pipelines — each connected cluster of shared address + tax-ID + beneficial-owner is one 'island' the compliance team treats as a single customer.

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

Practice these live with InterviewChamp.AI →