Skip to main content

14. Number of Islands

mediumAsked at Nubank

Count connected components of '1's in a 2D grid; Nubank uses it as an analog for clustering related KYC/fraud accounts on a relationship grid.

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

Problem

Given an m x n 2D grid where '1' is land and '0' is water, return the number of islands. An island is a maximal group of horizontally/vertically adjacent land cells.

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","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Output
1

Approaches

1. Union-Find

Union each land cell with neighbors; count distinct roots.

Time
O(m*n*alpha)
Space
O(m*n)
// Init parent[] for every land; for each land cell union with right and down neighbors; count distinct find(i).

Tradeoff:

2. DFS flood-fill

Sweep the grid; when you hit a '1', DFS-sink the whole island to '0' and increment the counter. Each cell is visited once.

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

Tradeoff:

Nubank-specific tips

Nubank likes when you call out that mutating input is fine for a screen but you'd clone the grid for a production fraud pipeline — they take infra hygiene seriously.

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

Practice these live with InterviewChamp.AI →