Skip to main content

200. Number of Islands

mediumAsked at Hugging Face

Count connected components of '1's in a binary grid. Hugging Face uses this BFS/DFS graph traversal problem to probe spatial reasoning — the same connected-component logic used to identify coherent token clusters in attention heat maps or connected regions in image-segmentation datasets.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2026-Q1)— Appears in Hugging Face SWE onsite reports as a standard graph traversal medium problem.
  • Blind (2025-11)— Hugging Face interview threads cite Number of Islands as a high-frequency medium for ML infrastructure and backend roles.

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 connected land cells form 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 connected components of land.

Approaches

1. DFS with in-place marking

Iterate over all cells. When a '1' is found, increment the count and DFS to mark all connected land cells as '0' (visited). Each DFS call floods an entire island.

Time
O(m*n)
Space
O(m*n) worst-case call stack
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'; // mark visited
    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: O(m*n) time, O(m*n) stack space in the worst case (entire grid is land). Elegant and concise. If stack overflow is a concern (very large grids), use iterative BFS.

2. BFS with queue

Same logic but use an explicit queue to avoid deep recursion. Mark cells visited when enqueuing (not dequeuing) to prevent duplicates.

Time
O(m*n)
Space
O(min(m,n)) for BFS queue
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 [row, col] = queue.shift();
        for (const [dr, dc] of dirs) {
          const nr = row + dr, nc = col + 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: O(m*n) time, O(min(m,n)) space for the BFS queue (the queue never holds more than the boundary of the current island). Preferred when the grid is large and stack overflow is a real risk.

Hugging Face-specific tips

Hugging Face will ask: 'What if you can't mutate the grid?' Use a visited Set of (r,c) string keys. Also ask: 'What if the grid is distributed across multiple machines?' Then pivot to Union-Find for merging results across partitions. Connect to their domain: 'Connected-component labeling is exactly how we identify contiguous highlighted regions in attention visualization — the same flood-fill logic applied to token attention matrices.'

Common mistakes

  • Not marking cells as visited (setting to '0') before or during traversal — causes infinite loops.
  • Checking bounds after accessing the cell — always check bounds first to avoid index-out-of-range.
  • Counting a cell as a new island before verifying it's '1'.
  • In BFS, marking cells visited when dequeuing instead of enqueuing — causes the same cell to be enqueued multiple times.

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • Max Area of Island (LC 695) — return the largest island area instead of the count.
  • Number of Islands II (LC 305) — islands are added one at a time; use Union-Find for dynamic connectivity.
  • How would you count islands in a grid too large to fit in memory?

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 as '0' instead of using a separate visited array?

It avoids allocating O(m*n) extra space. If the original grid must be preserved, use a boolean visited array or a Set.

What is the space complexity of DFS vs BFS?

DFS worst case is O(m*n) call stack (all land). BFS worst case is O(min(m,n)) queue size (diagonal boundary of an island). BFS is strictly better for space in pathological inputs.

Can Union-Find solve this?

Yes — initialize each land cell as its own component, then union horizontally and vertically adjacent land cells. The number of distinct roots = number of islands. Useful for the dynamic-insertion variant.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →