Skip to main content

200. Number of Islands

mediumAsked at Pinterest

Number of Islands is Pinterest's canonical graph-traversal problem: given a 2D grid of '1's (land) and '0's (water), count the distinct islands. The interviewer wants either BFS or DFS flood-fill — pick one, narrate the traversal invariant, ship.

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

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

  • Glassdoor (2026-Q1)— Pinterest SWE onsite reports list Number of Islands in the graph/traversal round for backend SWEs.
  • LeetCode Pinterest tag (2026-Q1)— High-frequency entry on the Pinterest company-tagged problem list.
  • Reddit r/cscareerquestions (2025-11)— Pinterest L4 onsite reports cite this as a 30-minute traversal warm-up.

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. 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

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 flood-fill (recursive)

Iterate every cell. When you hit a '1', recursively sink the entire connected component to '0' and increment the count.

Time
O(m * n)
Space
O(m * n) worst case for recursion stack
function numIslandsDfs(grid) {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;
  function sink(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '0';
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
  }
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count += 1;
        sink(r, c);
      }
    }
  }
  return count;
}

Tradeoff: Cleanest code. Risk: 300x300 grid is at the recursion-depth ceiling for JS engines on a worst-case 'snake' island. Convert to iterative if interviewer flags it.

2. BFS flood-fill (iterative)

Same outer scan; when you hit a '1', BFS with a queue marking visited and increment the count.

Time
O(m * n)
Space
O(min(m, n)) for the BFS frontier
function numIslandsBfs(grid) {
  const rows = grid.length, cols = grid[0].length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue;
      count += 1;
      const q = [[r, c]];
      grid[r][c] = '0';
      while (q.length) {
        const [cr, cc] = q.shift();
        for (const [dr, dc] of dirs) {
          const nr = cr + dr, nc = cc + dc;
          if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
          if (grid[nr][nc] !== '1') continue;
          grid[nr][nc] = '0';
          q.push([nr, nc]);
        }
      }
    }
  }
  return count;
}

Tradeoff: No recursion-depth risk; constant-extra space proportional to the BFS frontier rather than the whole component. Best default for unknown grid sizes.

Pinterest-specific tips

Pinterest doesn't have a strong DFS-vs-BFS preference for this problem, but they will ask the follow-up: 'what if I don't want to mutate the input?' Answer: a visited Set keyed by 'r,c' (or a parallel boolean matrix) with the same traversal. Volunteer the mutate-or-set tradeoff upfront so the interviewer knows you've thought about it.

Common mistakes

  • Comparing grid[r][c] to the number 1 instead of the string '1' — LeetCode passes characters, not ints.
  • Forgetting to mark cells visited inside the BFS frontier — without this you re-process and infinite-loop on cycles (irrelevant here since this is a tree, but it bites on the union-find variant).
  • Using q.shift() in tight loops — O(n) per shift in V8. Use a head pointer instead for very large grids.
  • Recursing on a 300x300 worst-case snake-shape grid — JS recursion limit blows up around ~10k frames.

Follow-up questions

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

  • Don't mutate the input grid — use a visited Set.
  • Count islands' shapes uniquely (LeetCode 694: Number of Distinct Islands).
  • Union-Find variant: stream of land-additions, count islands after each addition.
  • 8-directional connectivity (including diagonals).

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 use DFS or BFS in the interview?

Either is accepted. DFS is shorter to write; BFS has bounded stack depth. State both options out loud, pick BFS for safety on larger grids, and move on.

Why does Pinterest like this problem?

It's a clean signal on graph traversal which is foundational for the recommendation / clustering work at Pinterest. The follow-ups (Union-Find, streaming) test deeper graph fluency.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →