Skip to main content

200. Number of Islands

mediumAsked at Broadcom

Count connected components of land in a 2D grid. Broadcom asks this because graph connectivity is foundational to network-topology discovery — the same BFS/DFS that counts islands maps directly to identifying isolated segments in a physical switch topology or VLAN reachability analysis.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2026-Q1)— Reported as one of the most common graph problems in Broadcom SWE onsite rounds for networking software roles.
  • Blind (2025-12)— Broadcom threads cite Number of Islands as a near-guaranteed medium graph problem in onsite loops.

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 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 disconnected land masses.

Approaches

1. DFS (sink visited cells)

Iterate every cell. When a '1' is found, increment the island count and DFS to mark all connected land cells as visited (overwrite with '0'). Continue scanning.

Time
O(m * n)
Space
O(m * n) call stack worst case
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: O(m*n) time. Mutates the grid (acceptable in interviews; ask about immutability constraints). DFS stack depth is O(m*n) worst case — an all-land grid.

2. BFS (iterative, avoids deep stack)

Same outer scan, but use a queue for the flood-fill instead of recursion. Better for very large grids where recursion depth would overflow the call stack.

Time
O(m * n)
Space
O(min(m, n)) BFS queue width
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++;
      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 < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

Tradeoff: BFS queue space is bounded by the perimeter of the largest island — smaller than O(m*n) in practice. Preferred when stack depth is a constraint (large embedded systems context relevant to Broadcom).

Broadcom-specific tips

At Broadcom, connect this immediately to network topology: 'This is connected-component counting — the same primitive used in VLAN reachability and STP domain discovery.' If the interviewer asks about the mutation of grid, offer the visited-set alternative. Broadcom interviewers follow up with Union-Find (Disjoint Set Union) — be prepared to sketch how you'd use it for dynamic connectivity queries.

Common mistakes

  • Forgetting bounds checks before accessing grid[r][c] — causes index-out-of-bounds on edge cells.
  • Marking a cell visited after enqueueing instead of before — can enqueue the same cell multiple times.
  • Not handling the empty grid case — check rows === 0 or cols === 0.
  • Using a separate visited array unnecessarily when you can just overwrite the grid.

Follow-up questions

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

  • Max Area of Island (LC 695) — return the size of the largest island.
  • Surrounded Regions (LC 130) — fill enclosed regions.
  • How would you solve this for a distributed grid across multiple servers (distributed connected components)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Is it acceptable to mutate the grid?

In interviews, yes unless told otherwise. Proactively ask: 'Can I modify the grid in place, or should I use a separate visited structure?' Broadcom values this kind of clarifying question.

Which is better — DFS or BFS?

Both are O(m*n). DFS is simpler to code; BFS avoids stack-overflow on very large grids. In a kernel/embedded context (Broadcom firmware), BFS with a queue is safer.

How does Union-Find compare?

Union-Find processes cells incrementally and supports dynamic connectivity queries. It's O(m*n * α(m*n)) — effectively O(m*n) — but more complex to implement correctly. Mention it as an extension if asked about dynamic updates.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →