Skip to main content

200. Number of Islands

mediumAsked at Robinhood

Given a 2D grid of '1's (land) and '0's (water), count the number of islands. Robinhood asks this as the canonical graph-traversal problem; the right answer is BFS/DFS over a 4-connected grid with a clean visited-marking strategy.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

  • Glassdoor (2026-Q1)— Robinhood SWE phone-screen and onsite reports include Number of Islands as a recurring graph problem.
  • Blind (2025-12)— Robinhood new-grad trip reports name BFS/DFS on grids as a thematic favorite.

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

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

Approaches

1. DFS with in-place marking

Iterate every cell. On a '1', start DFS to flood-fill the island, marking visited cells as '0'. Increment island count.

Time
O(m*n)
Space
O(m*n) recursion worst case
function numIslandsDFS(grid) {
  if (!grid.length) 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] !== '1') 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') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff: Cleanest code. Mutates the input — call this out so the interviewer can decide if that's acceptable (use a visited Set otherwise). Recursion depth = grid size in the worst case (snake-shaped island).

2. BFS with queue

Same outer scan, but flood-fill each island via BFS queue to avoid recursion-depth issues.

Time
O(m*n)
Space
O(m*n) queue worst case
function numIslandsBFS(grid) {
  if (!grid.length) 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';
      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 < m && nc >= 0 && nc < n && grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

Tradeoff: Same O(m*n) total work. Safer than DFS for very large grids — no recursion depth limit. Slightly more code under interview pressure.

3. Union-Find

Initialize one component per land cell. Union with right and down neighbors. Final component count is the answer.

Time
O(m*n α(m*n))
Space
O(m*n)
class DSU {
  constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); this.rank = new Array(n).fill(0); this.count = n; }
  find(x) { while (this.parent[x] !== x) { this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; }
  union(a, b) {
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return;
    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra;
    else { this.parent[rb] = ra; this.rank[ra]++; }
    this.count--;
  }
}

function numIslandsUF(grid) {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0].length;
  const dsu = new DSU(m * n);
  let water = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '0') { water++; continue; }
      if (r + 1 < m && grid[r + 1][c] === '1') dsu.union(r * n + c, (r + 1) * n + c);
      if (c + 1 < n && grid[r][c + 1] === '1') dsu.union(r * n + c, r * n + c + 1);
    }
  }
  return dsu.count - water;
}

Tradeoff: Great when followed by 'now islands can appear/disappear over time' (LC 305). For this problem alone it's overkill — but the right pivot if asked the streaming variant.

Robinhood-specific tips

Robinhood interviewers will accept DFS or BFS for the base problem but probe two things: (1) what happens if the grid is huge (BFS to avoid stack overflow); (2) what if the grid mutates over time (Union-Find). Articulate the input-mutation tradeoff explicitly: 'I'm marking cells '0' to track visited; if you'd rather I keep the input immutable, I'll use a visited Set at +O(m*n) space.'

Common mistakes

  • Forgetting the 4 boundary checks at the top of DFS — index errors on edge cells.
  • Using DFS on a 300x300 grid (max constraint) where a long snake-shaped island causes recursion-depth issues in some runtimes.
  • Only checking right and down neighbors in DFS — you must check all four directions because cells are visited in row-major order but the DFS can come back through any side.

Follow-up questions

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

  • Number of Islands II (LC 305) — islands can appear; use Union-Find.
  • Max Area of Island (LC 695) — return area not count.
  • Surrounded Regions (LC 130) — flip '0's not connected to border.
  • Walls and Gates (LC 286) — multi-source BFS from gates.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Should I mutate the input or use a visited set?

Both are valid. Mutating saves O(m*n) space and is cleaner code. State which you're doing and offer to switch if the interviewer wants the input preserved.

DFS or BFS — does it matter?

Same time complexity. BFS is safer for huge inputs (no recursion-depth risk). DFS is cleaner code. Most interviewers don't care which you pick — pick the one you can write bug-free under pressure.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →