200. Number of Islands

Q: Should I prefer DFS or BFS on this problem?

DFS is cleaner to implement (3 fewer lines than BFS). BFS is safer for huge grids because it uses an O(min(m,n)) explicit queue instead of an O(m*n) call stack. The IBM-preferred answer states both and picks based on the constraint — at m,n <= 300, either passes.

Q: When does Union-Find win over BFS/DFS?

When the grid is being constructed incrementally and you need to maintain the island count after each cell flips on (the LeetCode 305 follow-up). UF supports near-O(1) connectivity queries; redoing BFS after each cell flip would be O(m*n) per query.

mediumAsked at IBM

Number of Islands is IBM's graph-traversal screener — a 2D grid where each connected region of land cells counts as one island. The interviewer is grading whether you pick BFS or DFS deliberately, articulate the stack-depth risk on huge maps, and handle the in-place vs visited-set trade.

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

Glassdoor (2026-Q1)— IBM SWE-2 / SWE-3 onsite recurring problem (graph-traversal track).
LeetCode (2026-Q1)— Top-20 IBM-tagged problem (medium tier).
GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive with BFS/DFS variants.

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

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

Approaches

1. DFS with grid mutation as visited marker

Walk the grid. On each unvisited '1', increment the counter and DFS to sink the whole island by overwriting '1's to '0'.

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

function numIslandsDFS(grid) {
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;
  const sink = (r, c) => {
    if (r < 0 || r >= m || c < 0 || c >= n || 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 < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        count++;
        sink(r, c);
      }
    }
  }
  return count;
}

Tradeoff: Cleanest implementation and the most-common interview answer. Mutates the input grid (acceptable if explicitly noted). Risks stack overflow on a 300x300 all-land grid (90,000 deep recursion). Mention BFS as the safer alternative when grids could be larger.

2. BFS with explicit queue

Same outer loop; instead of recursion, push neighbors onto an explicit queue and process iteratively.

Time: O(m * n)
Space: O(min(m, n)) queue worst case

function numIslands(grid) {
  const m = grid.length;
  const 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';
      while (queue.length > 0) {
        const [cr, cc] = queue.shift();
        for (const [dr, dc] of dirs) {
          const nr = cr + dr;
          const 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: Iterative BFS — no recursion-stack risk. O(min(m,n)) queue size in the worst-case island shape. This is the IBM-preferred answer on the senior loop because it scales to grids larger than the call-stack limit.

3. Union-Find (disjoint-set)

Map each land cell to a set. Union with each land neighbor. Final number of sets = answer.

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

function numIslandsUF(grid) {
  const m = grid.length;
  const 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);
    const 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;
      if (r > 0 && grid[r - 1][c] === '1' && union(idx, (r - 1) * n + c)) count--;
      if (c > 0 && grid[r][c - 1] === '1' && union(idx, r * n + c - 1)) count--;
    }
  }
  return count;
}

Tradeoff: Nearly O(m*n) thanks to path compression + union by rank. Doesn't mutate the input grid. The right answer if the follow-up is 'what if the grid is streaming and cells light up over time?' — union-find handles incremental connectivity in nearly constant time per update.

IBM-specific tips

IBM grades the EXPLICIT choice between BFS and DFS on this problem. Saying 'I'll go DFS because the implementation is cleaner; on grids larger than ~10^5 cells I'd switch to BFS to avoid stack overflow' shows you've actually thought about the tradeoff. Bonus: mention union-find as the third approach if the interviewer pivots to incremental connectivity (relevant to IBM Cloud network-topology problems).

Common mistakes

Forgetting to mark cells as visited — infinite loop on cycles.
Using a Set keyed by 'r,c' string instead of mutating the grid — works but slow due to string allocation.
Counting islands on the inner DFS instead of the outer loop — double-counts.
Missing one of the four directions (often the diagonal — but the problem says only horizontal/vertical).
Using Array.shift() on a large queue — O(n) per shift; switch to a head-index variable for true O(1) dequeue.

Follow-up questions

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

Number of Islands II — streaming variant (LeetCode 305) — union-find shines.
Max Area of Island — return the area of the largest island instead of the count (LeetCode 695).
Surrounded Regions (LeetCode 130) — flip enclosed 'O's to 'X's.
Diagonal connectivity — what changes if diagonal neighbors also count?

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 prefer DFS or BFS on this problem?

DFS is cleaner to implement (3 fewer lines than BFS). BFS is safer for huge grids because it uses an O(min(m,n)) explicit queue instead of an O(m*n) call stack. The IBM-preferred answer states both and picks based on the constraint — at m,n <= 300, either passes.

When does Union-Find win over BFS/DFS?

When the grid is being constructed incrementally and you need to maintain the island count after each cell flips on (the LeetCode 305 follow-up). UF supports near-O(1) connectivity queries; redoing BFS after each cell flip would be O(m*n) per query.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →