Skip to main content

17. Number of Islands

mediumAsked at Asana

Count connected land regions in a 2-D grid — Asana maps this directly to identifying isolated clusters of tasks or teams in a project dependency graph where no cross-team links exist.

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 formed by connecting adjacent land cells 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"],["0","1","0"],["1","0","0"]]
Output
2

Explanation: Top cluster of four connected 1s is one island; the bottom-left 1 is another.

Example 2

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

Explanation: Two isolated land cells, each its own island.

Approaches

1. DFS flood-fill

For each unvisited land cell, trigger a DFS that marks all reachable land as visited. Count how many times you start a new DFS.

Time
O(m * n)
Space
O(m * n)
function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // mark visited
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff:

2. BFS flood-fill (optimal for large grids)

Use a queue instead of recursion — avoids call-stack overflow on large grids and is equally O(m*n).

Time
O(m * n)
Space
O(min(m, n))
function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue;
      count++;
      grid[r][c] = '0';
      const queue = [[r, c]];
      while (queue.length > 0) {
        const [cr, cc] = queue.shift();
        for (const [dr, dc] of dirs) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

Asana-specific tips

Asana interviewers use this to gauge graph-traversal fluency. Mention that mutating the grid in-place avoids an extra visited matrix (a memory win), but that in production you'd pass a copy to preserve the caller's data. BFS shines when the grid is very large — DFS risks stack overflow at 300x300. Naming the pattern 'connected components via flood-fill' scores points.

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

Practice these live with InterviewChamp.AI →