Skip to main content

21. Number of Islands

mediumAsked at Monzo

Count clusters of related accounts in a grid of customer/merchant connections.

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

Problem

Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands 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 = [["1","1","1"],["1","1","1"]]
Output
1

Approaches

1. Iterative BFS

Scan; on each unvisited land cell, BFS from it and mark the whole island, counting one island per BFS.

Time
O(m*n)
Space
O(min(m,n))
let count = 0;
for (let r = 0; r < grid.length; r++)
  for (let c = 0; c < grid[0].length; c++)
    if (grid[r][c] === '1') { count++; const q = [[r,c]]; while (q.length) { const [i,j] = q.shift(); if (grid[i]?.[j] !== '1') continue; grid[i][j] = '0'; q.push([i+1,j],[i-1,j],[i,j+1],[i,j-1]); } }
return count;

Tradeoff:

2. DFS flood-fill

Sink each connected component recursively, incrementing the island count once per new land cell discovered.

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

Tradeoff:

Monzo-specific tips

Monzo asks this in a fraud-clustering frame; mention how the same algorithm groups linked accounts on the ledger graph.

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

Practice these live with InterviewChamp.AI →