Skip to main content

200. Number of Islands

mediumAsked at Elastic

Count connected components of '1' cells in a 2D grid. Elastic reaches for this problem because BFS/DFS on a grid is a direct analogue of cluster connectivity analysis — the same reasoning applies when determining which Elasticsearch nodes belong to the same cluster partition after a network split.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2026-Q1)— Elastic SWE candidates report graph traversal and connected-component problems appearing in mid-level onsite rounds.
  • Blind (2025-10)— Number of Islands cited in Elastic interview prep threads as a standard graph question before harder distributed-topology discussions.

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

Explanation: All land cells are connected into one island.

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

Explanation: Three separate groups of connected land cells.

Approaches

1. DFS — mark and count

Iterate every cell. When a '1' is found, increment the island count and DFS to mark all connected land cells as visited (set to '0' or a visited marker). Each DFS call sinks the entire island.

Time
O(m * n)
Space
O(m * n) for recursion stack in worst case
function numIslands(grid) {
  let count = 0;
  const m = grid.length, n = grid[0].length;
  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // mark visited
    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: Clean and direct. Mutates the grid (acceptable if the problem allows it). For very large grids (300×300 = 90000 cells), the recursion depth can reach 90000 — mention iterative BFS as the safe alternative.

2. BFS — iterative

Same outer loop. When a '1' is found, use a queue for BFS instead of DFS recursion. Enqueue the starting cell, mark it, then process neighbors level by level.

Time
O(m * n)
Space
O(min(m, n)) for queue in worst case
function numIslands(grid) {
  let count = 0;
  const m = grid.length, n = grid[0].length;
  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') {
        count++;
        grid[r][c] = '0';
        const queue = [[r, c]];
        while (queue.length > 0) {
          const [row, col] = queue.shift();
          for (const [dr, dc] of dirs) {
            const nr = row + dr, nc = col + 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: Avoids recursion stack overflow. Queue size is bounded by the perimeter of the island — O(min(m,n)) in practice. Preferred for large grids or production implementations.

Elastic-specific tips

Elastic interviewers often follow up with: 'How would you count islands in a grid that is distributed across multiple machines?' Describe Union-Find with path compression: each machine processes its local cells and sends border-cell information to a coordinator that merges components. This parallels how Elasticsearch handles cluster split-brain detection and re-merging after a partition heals.

Common mistakes

  • Not marking cells as visited before enqueueing — cells can be enqueued multiple times, leading to incorrect counts.
  • Forgetting bounds checks — always validate r >= 0 && r < m && c >= 0 && c < n before accessing grid[r][c].
  • Counting diagonally adjacent cells as connected — the problem specifies horizontal and vertical only.
  • Mutating the grid without noting this side effect — mention it to the interviewer and offer a visited array if mutation is not allowed.

Follow-up questions

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

  • Max Area of Island (LC 695) — find the island with the largest area instead of counting islands.
  • Number of Provinces (LC 547) — same problem on an adjacency matrix (connected components in a graph).
  • How would you solve this with Union-Find (Disjoint Set Union)?

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 set grid[r][c] = '0' instead of using a visited array?

Mutating in-place avoids allocating an O(m*n) boolean array. If the problem requires the grid to be unchanged, use a separate visited set.

Why is BFS preferred over DFS for very large grids?

DFS uses O(m*n) call stack in the worst case (a snake-shaped island). BFS uses a heap-allocated queue, avoiding stack overflow on large inputs.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →