Skip to main content

200. Number of Islands

mediumAsked at Anduril

Count the number of distinct land masses in a binary grid. Anduril asks this because graph traversal on a grid is the foundation of obstacle-map parsing and terrain-segmentation algorithms used in autonomous navigation — engineers need to demonstrate clean BFS/DFS reasoning on 2D state spaces.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2026-Q1)— Reported as a common medium in Anduril SWE onsite rounds with a 2D grid traversal focus.
  • Blind (2025-12)— Anduril candidates mention Number of Islands as a high-frequency graph traversal question across multiple role types.

Problem

Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

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

Explanation: All '1's are connected into a single island.

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

Explanation: Three separate islands.

Approaches

1. DFS with in-place marking

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

Time
O(m*n)
Space
O(m*n) worst-case call stack
function numIslands(grid) {
  let count = 0;
  const rows = grid.length, cols = grid[0].length;
  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: Clean and concise. Mutates the input grid — ask the interviewer if that's acceptable. Stack depth is O(m*n) in the worst case (a grid entirely of '1's).

2. BFS with queue

Use an explicit queue to avoid deep recursion. For each unvisited '1', BFS the connected component.

Time
O(m*n)
Space
O(min(m,n)) queue
function numIslands(grid) {
  let count = 0;
  const rows = grid.length, cols = grid[0].length;
  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) {
        const [cr, cc] = queue.shift();
        for (const [dr, dc] of dirs) {
          const nr = cr + dr, 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: Avoids call-stack depth issues — preferred at Anduril for large grids. The queue holds at most O(min(m,n)) entries at its widest diagonal. Note: queue.shift() is O(n) for arrays; use a proper deque or pointer-based queue for production code.

Anduril-specific tips

Anduril engineers care about memory and stack safety. Mention the BFS vs DFS tradeoff explicitly: 'DFS is simpler but has O(m*n) stack depth risk on a fully filled grid. BFS uses an explicit queue and is safer for large inputs.' Ask permission before mutating the grid; if not allowed, use a visited boolean matrix. Also connect to real use: 'This is connected-components detection on a grid — the same primitive used in obstacle-map segmentation.'

Common mistakes

  • Forgetting to mark cells visited before enqueueing (not after dequeuing) — causes the same cell to be enqueued multiple times.
  • Checking grid[r][c] === 1 (number) instead of '1' (string) — the grid contains string characters.
  • Not handling edge/corner cells — the bounds check (r >= 0, r < rows, etc.) must be done before accessing grid[r][c].
  • Mutating the input without telling the interviewer — always ask whether in-place modification is acceptable.

Follow-up questions

An interviewer at Anduril may pivot to one of these next:

  • Max area of island (LC 695) — instead of counting islands, find the one with the most cells.
  • Pacific Atlantic Water Flow (LC 417) — reverse the graph direction.
  • How would you count islands if the grid is distributed across multiple machines?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why mark cells as '0' instead of using a visited set?

Mutating in place avoids the O(m*n) extra space of a visited matrix. It's only valid if the caller doesn't need the original grid.

What is the time complexity?

Every cell is visited at most once — O(m*n) total, regardless of how many islands there are.

Should I use DFS or BFS?

Both are O(m*n). DFS is simpler to write. BFS avoids deep recursion and is preferable in production code or when grid dimensions are large.

Practice these live with InterviewChamp.AI

Drill Number of Islands and other Anduril interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →