200. Number of Islands

Q: Why does Cisco favor this problem?

Cisco's bread and butter is network topology. Number of Islands is the simplest grid-graph problem that maps directly onto 'partition this grid of devices into reachable segments.' The interviewer can extend it in many directions (largest island, diagonal connectivity, streaming) without having to switch problems.

Q: Should I default to DFS or BFS?

DFS is the shorter code, so it's the default for a 30-minute slot. But state out loud that BFS is the version you'd ship to production for grids that exceed your call-stack budget — Cisco rewards that production sensibility.

Q: Is in-place mutation acceptable?

Almost always — but always ASK first. Some Cisco interviewers explicitly want to see the visited-Set pattern because it's safer in real codebases where the caller doesn't expect the input to change.

mediumAsked at Cisco

Number of Islands is Cisco's most recurring graph-DFS question because it maps almost one-to-one onto a real Cisco engineering task: partitioning a grid of nodes into connected network segments. The interviewer is checking whether you reach for DFS or BFS without hesitation and whether you mutate-in-place or use a visited set.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Cisco loops.

Glassdoor (2026-Q1)— Appears in Cisco Software Engineer onsite reports as a 30-minute coding round.
Levels.fyi (2025-12)— Cited by Cisco SDE-II candidates as a recurring grid-graph problem.
Blind (2025-11)— Cisco interview thread lists Number of Islands as the typical first round for new-grad and L4 IC 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","0"],["1","1","0"],["0","0","1"]]

Output

Explanation: Top-left 2x2 block is one island; the lone '1' in the bottom-right is another.

Example 2

Input

grid = [["1","1","1"],["0","1","0"],["1","1","1"]]

Output

Explanation: All land cells are 4-directionally connected.

Approaches

1. Brute-force flood-fill with visited set

Scan every cell. When you hit an unvisited '1', flood-fill via DFS using a separate visited Set; increment counter.

Time: O(m*n)
Space: O(m*n)

function numIslandsBrute(grid) {
  const m = grid.length, n = grid[0].length;
  const visited = new Set();
  let count = 0;
  function dfs(r, c) {
    const key = r * n + c;
    if (r < 0 || r >= m || c < 0 || c >= n) return;
    if (grid[r][c] === '0' || visited.has(key)) return;
    visited.add(key);
    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' && !visited.has(r * n + c)) {
        dfs(r, c);
        count++;
      }
    }
  }
  return count;
}

Tradeoff: Same Big-O as the optimal but allocates an O(m*n) Set. Use this when the interviewer explicitly forbids mutating the input grid.

2. In-place DFS (optimal)

Same scan, but sink each visited '1' to '0' so the grid itself becomes the visited record. No extra hash structure required.

Time: O(m*n)
Space: O(m*n) worst-case recursion stack

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

Tradeoff: Eliminates the visited-Set allocation; recursion still costs O(m*n) on a fully-land grid because the call stack can be that deep. Cisco interviewers often follow up with 'what if the grid is 10^6 x 10^6?' to push you toward iterative BFS.

3. Iterative BFS (avoids stack overflow)

Replace recursion with an explicit queue. Same Big-O, but bounded heap usage rather than call stack.

Time: O(m*n)
Space: O(min(m, n))

function numIslandsBFS(grid) {
  if (!grid || grid.length === 0) return 0;
  const m = grid.length, n = grid[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  let count = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] !== '1') continue;
      count++;
      const queue = [[r, c]];
      grid[r][c] = '0';
      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 >= m || nc < 0 || nc >= n) continue;
          if (grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

Tradeoff: BFS queue is bounded by the frontier (O(min(m, n)) for a snake-shaped island), so this is the version you write when the interviewer asks about very large grids.

Cisco-specific tips

Cisco interviewers reward you for naming the network-topology framing out loud — 'each connected component is a network segment, so this is a connected-components count on a 4-neighborhood grid graph.' Ask explicitly whether you can mutate the input; if yes, use in-place DFS. If the interviewer pushes back with 'what about a 10^6 grid?', pivot to BFS and explain the stack-overflow risk with recursion at that scale.

Common mistakes

Forgetting to mark a cell as visited BEFORE you recurse into it — leads to revisits and on some inputs an infinite loop.
Using `queue.shift()` (O(n) on JS arrays) for very large BFS — for actual scale you'd swap in a proper deque or use two stacks.
Counting diagonals as connected — the problem specifies only 4-directional (up/down/left/right) adjacency.

Follow-up questions

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

What if islands can connect diagonally? (Add 4 more directions to the dirs array.)
Count the AREA of the largest island instead of the count. (LC 695 — track size during the DFS.)
What if the grid streams in row-by-row and you can't hold it all in memory? (Union-Find with rolling rows.)
Count distinct island SHAPES (LC 694) — track the DFS traversal path as a canonical signature.

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 does Cisco favor this problem?

Cisco's bread and butter is network topology. Number of Islands is the simplest grid-graph problem that maps directly onto 'partition this grid of devices into reachable segments.' The interviewer can extend it in many directions (largest island, diagonal connectivity, streaming) without having to switch problems.

Should I default to DFS or BFS?

DFS is the shorter code, so it's the default for a 30-minute slot. But state out loud that BFS is the version you'd ship to production for grids that exceed your call-stack budget — Cisco rewards that production sensibility.

Is in-place mutation acceptable?

Almost always — but always ASK first. Some Cisco interviewers explicitly want to see the visited-Set pattern because it's safer in real codebases where the caller doesn't expect the input to change.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →