Skip to main content

200. Number of Islands

mediumAsked at AMD

Count the number of islands in a 2D grid. AMD uses BFS/DFS grid traversal to test whether candidates understand connected-component analysis — a pattern that maps directly to GPU texture block connectivity, render target region detection, and cluster analysis in performance heat maps.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE candidates report Number of Islands appearing in medium coding rounds, sometimes with a parallelization follow-up.
  • Blind (2025-10)— AMD interview threads list this as a BFS/DFS medium that AMD extends with GPU-parallel connected-component follow-ups.

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.

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

Approaches

1. DFS (flood fill, mutating grid)

Scan every cell. When '1' is found, increment count and DFS to mark the entire island as visited by setting cells to '0'.

Time
O(m * n)
Space
O(m * n) call stack worst case
function numIslands(grid) {
  let count = 0;
  const 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. Mutates the grid in place — ask the interviewer if mutation is allowed. O(m*n) stack in the worst case (a snake-shaped island).

2. BFS (iterative, avoids deep call stack)

Same outer scan, but use a queue for BFS flood fill instead of recursion. Avoids stack overflow on large islands.

Time
O(m * n)
Space
O(min(m, n)) queue
function numIslands(grid) {
  let count = 0;
  const rows = grid.length, cols = grid[0].length;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        const queue = [[r, c]];
        grid[r][c] = '0';
        while (queue.length) {
          const [cr, cc] = queue.shift();
          for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
            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 deep recursion. Queue size is bounded by the perimeter of the island — O(min(m,n)) in the worst case for a diagonal strip. Preferred for large grids in production.

AMD-specific tips

AMD GPU engineers deal with connected-component labeling in image processing, texture compression, and render-region analysis. For the follow-up on parallelization: parallel BFS can be implemented using a frontier of active cells dispatched across GPU threads, with atomic operations to mark visited cells. Union-Find is another approach that parallelizes naturally. Mention these angles if the interviewer asks how this scales to a 4K texture grid.

Common mistakes

  • Not marking cells as visited before queuing them (BFS) — leads to queuing the same cell multiple times.
  • Using `=` instead of `===` for character comparison — '1' is a string in this problem.
  • Forgetting bounds checks in DFS — will throw on out-of-bounds array access.
  • Counting water cells that touch land — only '1' cells count as land.

Follow-up questions

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

  • Max Area of Island (LC 695) — return the area of the largest island.
  • Number of Enclaves (LC 1020) — count land cells that cannot reach the grid boundary.
  • How would you parallelize connected-component labeling for a large texture on a GPU?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Can I modify the grid?

Ask the interviewer. If mutation is allowed, marking visited cells with '0' avoids a separate visited matrix. If not, use a boolean 2D visited array.

BFS vs DFS — which is better here?

Both are O(m*n). BFS avoids deep call stacks for snake-shaped islands that could cause a stack overflow in DFS. For AMD's large-grid scenarios, BFS is safer.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →