Skip to main content

24. Number of Islands

mediumAsked at Unity

Count connected land regions in a 2D grid — the same flood-fill Unity's NavMesh baker uses to identify isolated walkable surface patches before stitching them into a navigation graph.

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

Problem

Given an m x n 2D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Constraints

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

Examples

Example 1

Input
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Output
1

Example 2

Input
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output
3

Approaches

1. DFS flood fill (in-place mark)

For each unvisited '1', increment count and DFS to mark the whole island as visited by setting cells to '0'.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  let count = 0;
  function dfs(r, c) {
    if (r < 0 || r >= grid.length || c < 0 || 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:

2. BFS flood fill

Same idea with a queue instead of recursion stack. Safer for very large grids where DFS call depth could overflow.

Time
O(m*n)
Space
O(min(m,n))
function numIslands(grid) {
  let count = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] !== '1') continue;
      count++;
      grid[r][c] = '0';
      const queue = [[r, c]];
      while (queue.length) {
        const [cr, cc] = queue.shift();
        for (const [dr, dc] of dirs) {
          const nr = cr + dr, nc = cc + dc;
          if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

Unity-specific tips

Unity specifically probes whether you'd choose BFS over DFS for large terrain grids — DFS can hit JS call-stack limits on 300×300 grids. Frame your preference around stack-overflow safety, which maps directly to why Unity's NavMesh baker uses iterative flood-fill internally.

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

Practice these live with InterviewChamp.AI →