Skip to main content

200. Number of Islands

mediumAsked at Shopify

Number of Islands is Shopify's canonical graph-traversal interview. The interviewer grades whether you reach for BFS or DFS naturally and discuss the stack-overflow risk on huge grids.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Backend Developer + Production Engineer onsites cite this as the standard grid-DFS round.
  • Reddit r/cscareerquestions (2025-11)— Shopify new-grad reports include this with the Union-Find follow-up.

Problem

Given an m x n 2D binary grid 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 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
2

Example 2

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

Explanation: Even though there's a hole, all land cells are connected through the center.

Approaches

1. Recursive DFS

Walk the grid; on a '1', increment count and DFS-flood-fill its connected component to '0' (or use a visited set).

Time
O(m*n)
Space
O(m*n) recursion depth worst case
function numIslandsDFS(grid) {
  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: Shortest correct version. Mutates the input grid (call it out to the interviewer). Risk: deep recursion on a 300x300 all-land grid -> 90,000 stack frames, which can blow the JS engine's stack.

2. Iterative BFS (queue-based, no stack-overflow risk)

Same logic but with a queue instead of recursion. Visit nodes level by level.

Time
O(m*n)
Space
O(min(m,n))
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  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 || grid[nr][nc] !== '1') continue;
          grid[nr][nc] = '0';
          queue.push([nr, nc]);
        }
      }
    }
  }
  return count;
}

Tradeoff: No recursion -> no stack-overflow risk on huge grids. Slightly more verbose. Shopify senior candidates should default to this. Note: Array.shift is O(n); for true O(1) queue ops use a head-pointer deque, but for grid problems the constant factor rarely matters.

3. Union-Find

Treat each land cell as a node; union adjacent land cells. Final island count = number of connected components.

Time
O(m*n*a(m*n))
Space
O(m*n)
function numIslandsUF(grid) {
  const m = grid.length, n = grid[0].length;
  const parent = new Array(m * n).fill(-1);
  const rank = new Array(m * n).fill(0);
  let count = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        parent[r * n + c] = r * n + c;
        count++;
      }
    }
  }
  function find(x) {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
  }
  function union(a, b) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    if (rank[ra] < rank[rb]) parent[ra] = rb;
    else if (rank[ra] > rank[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
    count--;
    return true;
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] !== '1') continue;
      if (r + 1 < m && grid[r + 1][c] === '1') union(r * n + c, (r + 1) * n + c);
      if (c + 1 < n && grid[r][c + 1] === '1') union(r * n + c, r * n + c + 1);
    }
  }
  return count;
}

Tradeoff: Same asymptotic complexity, but the constant factor is higher. Bring it up only if the follow-up is 'now add a method that handles cells flipping to land one at a time' — that's where Union-Find shines.

Shopify-specific tips

Shopify's grading bar: name DFS, BFS, AND Union-Find. Pick one, but explain when each wins. Expected follow-up: 'now imagine cells turn from water to land one at a time, report island count after each' (LeetCode 305) — Union-Find is the answer. Default to BFS for the canonical write-up because it dodges the stack-overflow risk.

Common mistakes

  • Forgetting to mark the starting cell as visited (causes infinite recursion).
  • Marking cells AFTER recursing into them — double-counts neighbors.
  • Forgetting to check bounds — index errors.
  • Using grid[r][c] === 1 (number) when the input is '1' (string) — fails silently.

Follow-up questions

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

  • Number of Islands II (LeetCode 305) — cells turn from water to land online. Union-Find required.
  • Max area of an island.
  • Count distinct island shapes (translation-equivalent).
  • Surrounded Regions (LeetCode 130) — flip cells via boundary DFS.
  • Pacific Atlantic Water Flow (LeetCode 417) — multi-source BFS.

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 grid or use a visited set?

Both are correct. Mutating is O(1) extra memory (after the recursion stack) but destroys the input — explicitly tell the interviewer. A visited Set is O(m*n) extra space but keeps the input clean. Shopify accepts either if you call it out.

DFS vs BFS — which does Shopify prefer?

Either works for correctness. BFS is safer because it avoids deep recursion. DFS is shorter to write. Senior candidates default to BFS; junior candidates can ship DFS if they note the stack-overflow risk.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →