Skip to main content

200. Number of Islands

mediumAsked at Akamai

Count connected components of land cells in a 2D grid. Akamai uses this to probe graph traversal skills — the same BFS/DFS component labeling appears in network topology analysis, where connected PoP clusters in an infrastructure map must be identified and counted.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2026-Q1)— Akamai SWE interview reports list Number of Islands as one of the most common graph traversal questions.
  • Blind (2025-10)— Akamai threads confirm BFS/DFS grid problems appear in both phone screens and onsite rounds.

Problem

Given an m x n 2D binary grid where '1' represents land and '0' represents 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 components.

Approaches

1. DFS with in-place marking

Scan the grid. When a '1' is found, increment the island count and DFS to mark all connected '1's as visited (change to '0' in place). Continue scanning.

Time
O(m * n)
Space
O(m * n) worst-case DFS stack
function numIslands(grid) {
  let count = 0;
  const rows = grid.length;
  const 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. In-place marking avoids a separate visited array (O(1) extra space) but mutates the input. Always note the mutation to the interviewer and offer to use a visited set if immutability is required.

2. BFS with queue

Same scan, but use an explicit queue (iterative BFS) instead of DFS recursion. Avoids call stack overflow on large all-land grids (300×300 = 90,000 cells deep).

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

Tradeoff: BFS avoids the recursive call stack, which can overflow for large fully-connected grids. Akamai may ask about stack overflow risk — mentioning BFS as the safer production choice is a differentiator.

Akamai-specific tips

Proactively discuss the mutating-input trade-off: 'I'm marking cells as visited in place by changing 1 to 0. This is O(1) extra space but modifies the caller's grid. If immutability is required, I'd use a separate boolean visited array.' Akamai values awareness of API contracts and side-effect safety, which comes directly from their C/C++ systems background.

Common mistakes

  • Forgetting bounds checks in DFS — accessing out-of-range indices causes errors; check before recursing.
  • Not marking the cell visited before the recursive calls — causes infinite loops on grids with cycles (though grids are acyclic, developing the habit prevents bugs in general graphs).
  • Using a visited Set with array keys — JavaScript arrays are objects; [r,c].toString() is needed for correct Set membership checks.

Follow-up questions

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

  • Max Area of Island (LC 695) — count cells per island and return the maximum.
  • Pacific Atlantic Water Flow (LC 417) — BFS from ocean boundaries.
  • How would you solve this in a distributed system where the grid is partitioned across machines?

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 in-place marking work without double-counting?

Once a cell is flipped from '1' to '0', it is never reconsidered by the outer scan. The DFS ensures all cells of an island are marked before the outer loop moves on.

When would DFS overflow the stack?

A 300×300 all-land grid creates a DFS chain of up to 90,000 frames. Most JavaScript engines allow ~10,000–15,000 frames before a stack overflow. BFS with an explicit queue avoids this entirely.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →