Skip to main content

200. Number of Islands

mediumAsked at Glean

Glean uses this to probe graph traversal fluency — BFS and DFS over a 2D grid mirror the connected-component analysis used in clustering semantically related documents into topic islands.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2026-Q1)— Glean engineering candidates report Number of Islands as a consistent medium in coding rounds.
  • Blind (2025-11)— Glean prep threads list this as a canonical graph-traversal problem that doubles as a connected-components test.

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
1

Explanation: All land cells are connected — 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 disconnected land masses.

Approaches

1. DFS with in-place marking

Scan each cell. When a '1' is found, increment the island count and use DFS to mark the entire connected component as visited by replacing '1' with '0'.

Time
O(m * n)
Space
O(m * n) worst-case call stack
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: O(m*n) time. In-place marking avoids a separate visited array. DFS call stack depth is bounded by the island size — worst case O(m*n) for a grid full of land.

2. BFS with queue

Same outer loop, but use a queue (BFS) to flood-fill each island iteratively. Eliminates deep recursion risk.

Time
O(m * n)
Space
O(min(m, n)) BFS queue
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++;
        const queue = [[r, c]];
        grid[r][c] = '0';
        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: BFS is iterative and avoids stack overflow on large grids. The queue holds at most O(min(m, n)) elements at any level. Prefer BFS in production; DFS is fine in an interview.

Glean-specific tips

Lead with 'this is a connected-components problem on a graph where cells are nodes and adjacency is the edges.' Glean engineers appreciate framing grid problems as graph problems — it shows you recognize the underlying structure. Mention the trade-off between DFS (simpler code, stack risk) and BFS (safer for large grids, iterative). If asked about distributed systems, pivot to: 'In a distributed index, you'd use Union-Find to cluster documents across shards without full graph traversal.'

Common mistakes

  • Not marking cells as visited before enqueuing in BFS — causes the same cell to be enqueued multiple times, leading to TLE or incorrect counts.
  • Only marking visited after dequeuing in DFS — same issue; mark when you first encounter the cell.
  • Forgetting to handle the case where grid is empty or grid[0] is empty.
  • Counting connected components by the number of '1' cells instead of the number of DFS/BFS starts — each DFS/BFS start is one island, not each cell.

Follow-up questions

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

  • Max Area of Island (LC 695) — return the size of the largest island instead of counting islands.
  • Number of Islands II (LC 305) — dynamic island insertion with Union-Find.
  • Pacific Atlantic Water Flow (LC 417) — multi-source BFS from both oceans simultaneously.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Is it safe to mutate the grid in-place?

In an interview it is fine — ask the interviewer first. If mutation is not allowed, use a separate boolean visited[][] matrix instead of overwriting '1' with '0'.

Why is BFS queue bounded by O(min(m, n))?

At any BFS level (wave front), the perimeter of a connected component grows no wider than the shorter grid dimension. Cells behind the wave front are already marked visited.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →