Skip to main content

18. Number of Islands

mediumAsked at Postman

Count connected components of land cells in a 2D grid.

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

Problem

Given an m x n 2D grid map of '1's (land) and '0's (water), return the number of islands. Islands are connected horizontally and 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"],["0","1","0"],["1","1","1"]]
Output
1

Approaches

1. Union-Find

Union each '1' cell with its neighbors, then count distinct roots.

Time
O(mn * α)
Space
O(mn)
// init parent[] for each cell, union with right and down neighbors when both '1'

Tradeoff:

2. DFS flood fill

Scan every cell; on a '1' bump the counter and DFS-fill the whole component to '0' so it's not recounted.

Time
O(mn)
Space
O(mn) worst case stack
function numIslands(g) {
  const r = g.length, c = g[0].length;
  let count = 0;
  const dfs = (i, j) => {
    if (i < 0 || j < 0 || i >= r || j >= c || g[i][j] !== '1') return;
    g[i][j] = '0';
    dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1);
  };
  for (let i = 0; i < r; i++)
    for (let j = 0; j < c; j++)
      if (g[i][j] === '1') { count++; dfs(i, j); }
  return count;
}

Tradeoff:

Postman-specific tips

Postman uses flood-fill thinking for connected-environment-variable reachability — they want you to be explicit about whether you mutate the input or copy it.

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

Practice these live with InterviewChamp.AI →