200. Number of Islands

Q: Why is in-place mutation OK here?

It's a tradeoff — saves O(m*n) for a visited matrix but destroys the input. Twilio panels generally accept it if you preempt: 'I'll mutate the grid for O(1) auxiliary; if immutability is required I'll allocate a visited grid.' Silent mutation without acknowledgment is a flag.

Q: When is Union-Find the right answer vs DFS?

DFS/BFS is faster and simpler for a one-shot count. Union-Find wins when you need to support incremental updates (add cells over time) or queries across multiple states without recomputing from scratch.

mediumAsked at Twilio

Number of Islands is Twilio's graph-traversal probe: given an m x n grid of '1' (land) and '0' (water), count distinct islands. The grading rubric weighs whether you reach for DFS/BFS to flood-fill or — more impressively — Union-Find for a streaming variant.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Twilio loops.

Glassdoor (2026-Q1)— Reported in Twilio backend SWE on-site rounds across multiple teams.
LeetCode Discuss (2025-12)— Cited in Twilio platform-engineering interview reports.

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 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","0"],["1","1","0"],["0","0","1"]]

Output

Example 2

Input

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

Output

Approaches

1. DFS flood-fill (canonical)

Scan the grid; on each unvisited '1', increment count and DFS to mark every connected land cell.

Time: O(m * n)
Space: O(m * n) worst-case recursion stack

function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  const dfs = (r, c) => {
    if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // mark visited in-place
    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: Each cell is visited once. Marking visited in-place avoids a separate visited matrix but mutates input — preempt the interviewer by saying 'I'll mutate the grid; we can deep-copy first if immutability is required'.

2. BFS flood-fill (stack-safe alternative)

Same idea as DFS but with an explicit queue — avoids deep recursion on long, thin islands.

Time: O(m * n)
Space: O(min(m, n))

function numIslandsBFS(grid) {
  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 q = [[r, c]];
      grid[r][c] = '0';
      while (q.length > 0) {
        const [cr, cc] = q.shift();
        for (const [dr, dc] of dirs) {
          const nr = cr + dr, nc = cc + dc;
          if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] !== '1') continue;
          grid[nr][nc] = '0';
          q.push([nr, nc]);
        }
      }
    }
  }
  return count;
}

Tradeoff: Same time complexity but avoids stack overflow on long, thin islands (worst case for DFS is m * n cells of recursion). BFS queue space is O(min(m, n)) for the perimeter. q.shift() is O(n) — for very large inputs use an index pointer instead.

3. Union-Find (extension for the streaming follow-up)

Initialize a Union-Find with one node per land cell. For each land cell, union it with land neighbors. Answer is the count of disjoint roots.

Time: O(m * n * α(m * n))
Space: O(m * n)

function numIslandsUF(grid) {
  const m = grid.length, n = grid[0].length;
  const parent = new Array(m * n).fill(0).map((_, i) => i);
  const rank = new Array(m * n).fill(0);
  let count = 0;
  const find = (x) => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
  const 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]++; }
    return true;
  };
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] !== '1') continue;
      count++;
      const idx = r * n + c;
      for (const [dr, dc] of [[1,0],[0,1]]) { // only check down + right to avoid double-union
        const nr = r + dr, nc = c + dc;
        if (nr >= m || nc >= n || grid[nr][nc] !== '1') continue;
        if (union(idx, nr * n + nc)) count--;
      }
    }
  }
  return count;
}

Tradeoff: α is the inverse Ackermann function — effectively constant. Union-Find shines when you need to ADD land incrementally (the streaming follow-up LC 305) because DFS would have to re-flood-fill from scratch each step.

Twilio-specific tips

Twilio reviewers grade Number of Islands on two dimensions: (1) you reach for DFS/BFS without prompting and articulate the 'visited' marking strategy, (2) you can extend to Union-Find when asked about the streaming variant (LC 305 — Number of Islands II, where land is added incrementally and you must report island count after each addition). State the input-mutation tradeoff up front so the interviewer knows you've considered it.

Common mistakes

Forgetting to mark visited — leads to infinite recursion or double-counting.
Using q.shift() in BFS without realizing it's O(n) — fine for LC's 300x300 grids, problematic at scale.
Recursing past grid bounds — guard before reading, not after; otherwise you read undefined and silently treat it as land.

Follow-up questions

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

What if islands are added one cell at a time (LC 305)? (Union-Find — each add either creates a new island or unions with neighbors.)
What if you needed to count DISTINCT island shapes, not just island count (LC 694)? (Normalize each island's shape by translation, hash as a frozen set of coords.)
How would you parallelize across machines? (Partition rows; merge by re-scanning the seam rows.)

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 is in-place mutation OK here?

It's a tradeoff — saves O(m*n) for a visited matrix but destroys the input. Twilio panels generally accept it if you preempt: 'I'll mutate the grid for O(1) auxiliary; if immutability is required I'll allocate a visited grid.' Silent mutation without acknowledgment is a flag.

When is Union-Find the right answer vs DFS?

DFS/BFS is faster and simpler for a one-shot count. Union-Find wins when you need to support incremental updates (add cells over time) or queries across multiple states without recomputing from scratch.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →