Skip to main content

15. Number of Islands

mediumAsked at N26

Count connected components of 1s in a 2D grid. N26 uses this as a stand-in for clustering related transactions during fraud-graph triage.

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

Problem

Given an m x n 2D grid of '1' (land) and '0' (water), return the number of islands. An island is land connected horizontally or vertically and surrounded by water.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Union-find

Union every adjacent land pair; count distinct roots at the end.

Time
O(m*n*alpha)
Space
O(m*n)
// build DSU, union each cell with right/down neighbor if both land.
// Return count of unique roots over land cells.

Tradeoff:

2. DFS flood fill

Walk the grid; when you hit unvisited land, increment the counter and DFS-mark every connected cell as visited. Each cell is touched once.

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

Tradeoff:

N26-specific tips

N26 cares that you call out the recursion-depth risk on a 300x300 grid and offer an iterative stack-based DFS as a fallback, since their fraud-graph workers run on lean Lambda containers.

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

Practice these live with InterviewChamp.AI →