Skip to main content

200. Number of Islands

mediumAsked at Citadel

Number of Islands is a graph traversal problem disguised as a 2D grid. At Citadel, graph connectivity appears in portfolio risk analysis (connected components of correlated positions) and in network topology modeling. The interview probes BFS vs DFS choice and whether you can modify the grid in-place to avoid a visited set.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

  • Glassdoor (2025-11)— Citadel SWE candidates report graph traversal problems including Number of Islands as regular fixtures in medium-difficulty coding rounds.
  • Blind (2025-09)— Citadel threads identify BFS/DFS grid problems as a reliable second-round category, testing graph fundamentals.

Problem

Given an m x n 2D binary grid 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 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 land cells are connected — one 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 connected land masses.

Approaches

1. DFS with in-place marking

Scan every cell. When a '1' is found, increment count and DFS to mark all connected land as '0' (visited). This avoids a separate visited set.

Time
O(m*n)
Space
O(m*n) worst-case call stack
function numIslands(grid) {
  let count = 0;
  const m = grid.length, n = grid[0].length;

  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || 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 < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff: O(m*n) time, O(m*n) call stack in the worst case (all land). Simple and clean. The in-place marking avoids O(m*n) visited array but mutates the input — always flag this to the interviewer.

2. BFS

Same structure as DFS but uses a queue. Preferred when stack depth is a concern — BFS has O(min(m,n)) queue depth in the worst case, much better than O(m*n) DFS recursion depth.

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

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

Tradeoff: BFS avoids deep recursion — important for very large grids. The queue depth is bounded by the island perimeter (O(min(m,n))), not the island area. Citadel will ask about stack depth — always mention BFS as the production-grade choice.

Citadel-specific tips

Always ask the interviewer: 'Is it acceptable to mutate the input grid?' If yes, in-place marking saves O(m*n) space. If no, allocate a visited Set. At Citadel, the BFS approach is preferred for production code because DFS recursion depth can hit JavaScript's call-stack limit on large grids (V8 default is ~10,000–15,000 frames). Make this argument explicitly — it shows low-latency systems awareness.

Common mistakes

  • Marking cells visited after pushing to the queue (BFS) rather than before — leads to duplicate queue entries and slower traversal.
  • Using '2' as the visited marker instead of '0' — either works, but '0' (water) is semantically cleaner and avoids needing a restore pass.
  • Forgetting bounds checks in DFS — going out of bounds causes an index error, not a graceful termination.
  • Using a new Set for visited instead of in-place marking — valid but O(m*n) extra space and slower due to Set overhead.

Follow-up questions

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

  • Max Area of Island (LC 695) — track size during DFS, return the maximum.
  • Number of Provinces (LC 547) — connected components in an adjacency matrix.
  • Surrounded Regions (LC 130) — mark everything connected to the border, then flip the rest.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

When would you use BFS over DFS?

BFS when the grid is very large and stack overflow is a risk. DFS when the island is guaranteed to be small or when the recursive code is more readable and maintainable.

What is the worst-case stack depth for DFS on this problem?

O(m*n) — if the entire grid is land and the DFS traverses in a spiral, the call stack can reach m*n frames. On a 300×300 grid that's 90,000 frames — a real risk in V8.

Does Union-Find work here?

Yes — Union-Find is a third approach that runs in O(m*n * α(m*n)) ≈ O(m*n) amortized. It's more complex to implement but useful when you need to query connectivity dynamically (not just count islands).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →