Skip to main content

200. Number of Islands

mediumAsked at DRW

DRW uses Number of Islands as a graph traversal proxy — the same connected-component logic appears in counterparty exposure clustering and in detecting isolated market segments. BFS and DFS both work; interviewers ask you to compare them on memory use.

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

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2025-Q4)— DRW SWE candidates report graph traversal problems including Number of Islands in onsite coding rounds.
  • Blind (2025-11)— DRW interview threads note this problem is used to test BFS vs DFS trade-offs, specifically around stack-depth risk on large grids.

Problem

Given an m × 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 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 land cells 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 distinct connected components.

Approaches

1. DFS (iterative with explicit stack)

Scan the grid. When a '1' is found, increment the count and perform a DFS to mark all connected land cells as visited (set to '0'). Use an explicit stack to avoid call-stack overflow on large grids.

Time
O(m×n)
Space
O(m×n) worst case stack
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  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') {
        count++;
        const stack = [[r, c]];
        grid[r][c] = '0';
        while (stack.length > 0) {
          const [cr, cc] = stack.pop();
          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';
              stack.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return count;
}

Tradeoff: O(m×n) time and space. Iterative DFS avoids call-stack overflow — important for 300×300 grids. Mutates the input grid for O(1) extra per-cell visited marker.

2. BFS

Same outer scan. Use a queue instead of a stack for BFS traversal. BFS finds shortest path to the boundary, which is useful for follow-up distance questions.

Time
O(m×n)
Space
O(min(m,n)) queue width
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  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') {
        count++;
        const queue = [[r, c]];
        grid[r][c] = '0';
        let head = 0;
        while (head < queue.length) {
          const [cr, cc] = queue[head++];
          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: Same O(m×n) time. BFS queue width is bounded by the island perimeter (O(min(m,n)) for thin islands). Use BFS when follow-ups involve shortest paths or distances.

DRW-specific tips

DRW interviewers specifically ask: 'Recursive DFS risks stack overflow on a 300×300 all-land grid — call stack depth could reach 90,000. How do you avoid that?' Iterative DFS or BFS with an explicit data structure. They also ask: 'How would you count islands in a streaming grid that grows row by row?' — that is the Union-Find approach, which processes one row at a time and merges components as new cells arrive.

Common mistakes

  • Using recursive DFS without noting the stack-overflow risk on large inputs.
  • Not marking cells as visited before pushing to the stack/queue — causes redundant pushes and inflated component size.
  • Forgetting to check grid boundaries before accessing grid[nr][nc].
  • Not restoring the grid if the problem requires non-destructive traversal — use a separate visited boolean array.

Follow-up questions

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

  • Max Area of Island (LC 695) — return the size of the largest island.
  • Number of Distinct Islands (LC 694) — count islands with distinct shapes using path signature hashing.
  • How would you count connected components as grid cells arrive in a live stream using Union-Find?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

BFS vs DFS for this problem?

Both give O(m×n). Use iterative DFS for simplicity. Use BFS if you need shortest-path distances (e.g., distance from land to water). BFS queue is bounded by island perimeter; DFS stack is bounded by island area.

Why mutate the grid?

Setting visited cells to '0' eliminates the need for a separate visited array, saving O(m×n) space. If the grid must be preserved, use a boolean visited array instead.

How does Union-Find compare?

Union-Find processes cells in any order with O(α(m×n)) per union/find (near O(1)). It is preferred for streaming or incremental updates where BFS/DFS would need to restart.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →