Skip to main content

200. Number of Islands

mediumAsked at Cohere

Count the number of connected components in a binary grid. Cohere asks this to test graph traversal — the same connected-component reasoning used when clustering retrieved document chunks into coherent topic groups.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2025-Q4)— Cohere SWE candidates note Number of Islands as a standard graph problem appearing in onsite rounds.
  • Blind (2025-10)— Cohere Blind threads list this as a recurring BFS/DFS medium problem.

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 1s 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 distinct islands.

Approaches

1. DFS with in-place marking

Iterate over every cell. When a '1' is found, increment the count and DFS to mark all connected '1' cells as '0' (visited). This avoids a separate visited matrix.

Time
O(m·n)
Space
O(m·n) call stack 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 intuitive. Stack depth can reach O(m·n) for a fully-land grid — risky for very large grids. Mutates input (restore if the caller requires the original grid).

2. BFS with queue

Same idea but use an explicit queue instead of recursion. Avoids call-stack overflow for large grids.

Time
O(m·n)
Space
O(min(m,n)) queue in the 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') continue;
      count++;
      const queue = [[r, c]];
      grid[r][c] = '0';
      while (queue.length) {
        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 call-stack overflow. BFS queue can still reach O(min(m,n)) in the worst case but is bounded by the island's frontier, not depth.

Cohere-specific tips

Cohere interviewers often extend this to 'how would you count connected document clusters in a similarity graph?' — the same connected-component algorithm applied to an adjacency matrix derived from embedding cosine similarities. Mention Union-Find as an alternative: O(m·n · α(m·n)) time, constant extra space after the disjoint-set array. If the grid is immutable, use a separate visited array instead of mutating the input.

Common mistakes

  • Not marking a cell visited before adding it to the BFS queue — causes the same cell to be enqueued multiple times.
  • Checking bounds after indexing — always bounds-check before accessing grid[nr][nc].
  • Forgetting to count the island before starting the traversal — increment count when the unvisited '1' is first discovered.
  • Using a 4-directional instead of 8-directional adjacency when the problem says horizontal/vertical only.

Follow-up questions

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

  • Max Area of Island (LC 695) — return the area of the largest island.
  • Number of Islands II (Union-Find streaming version) — islands are added incrementally.
  • How would you count connected document clusters given a cosine-similarity threshold?

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 mutate the grid instead of using a visited array?

It saves O(m·n) space. If the caller needs the original grid, use a separate boolean matrix or restore '0' cells to '1' after counting.

Which is better — DFS or BFS?

Both are O(m·n). BFS avoids call-stack overflow for very large grids and is preferred in production. DFS is more concise for interview settings.

Can Union-Find solve this?

Yes. Initialise a disjoint set for every '1', union adjacent '1' cells, then count distinct roots. This allows streaming additions (LC 305) without re-scanning the full grid.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →