Skip to main content

200. Number of Islands

mediumAsked at Linear

Count connected components of '1's in a 2D grid. Linear uses this as a graph traversal benchmark — both DFS and BFS are accepted, but the interviewer wants to hear you name the approach and explain the visited-cell marking strategy.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2026-Q1)— Consistently cited in Linear SWE onsite graph round reports.
  • Blind (2025-10)— Appears in multiple Linear interview threads as the canonical 2D grid traversal problem.

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

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

Approaches

1. DFS with in-place marking

Scan the grid; on finding an unvisited '1', increment count and DFS to mark the entire island as visited ('0' or '#').

Time
O(m * n)
Space
O(m * n)
function numIslands(grid) {
  let count = 0;
  function dfs(r, c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || 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 < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff: O(m*n) time, O(m*n) call stack in the worst case. Mutates the input grid — ask the interviewer if that's acceptable. If not, use a visited set or BFS with a queue.

2. BFS (no grid mutation)

Same scan but use a queue for BFS and a separate visited set to avoid mutating the grid.

Time
O(m * n)
Space
O(min(m, n))
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  const visited = new Set();
  let count = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  function bfs(r, c) {
    const q = [[r, c]];
    visited.add(`${r},${c}`);
    while (q.length) {
      const [row, col] = q.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' && !visited.has(`${nr},${nc}`)) {
          visited.add(`${nr},${nc}`);
          q.push([nr, nc]);
        }
      }
    }
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1' && !visited.has(`${r},${c}`)) {
        count++;
        bfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff: Does not mutate the grid. The queue at any given time holds at most the cells on the perimeter of the expanding island, which is O(min(m,n)) in a grid-shaped island.

Linear-specific tips

Before coding, ask: 'Is it okay to modify the grid?' This shows awareness of side effects — something Linear engineers care about in production code. If yes, DFS with in-place marking is the tightest solution. If no, use BFS with a visited set. Either way, name the pattern: 'flood fill / connected-component counting.'

Common mistakes

  • Not checking bounds before accessing grid[r][c] — out-of-bounds access will throw.
  • Mutating the grid without asking permission — the interviewer may penalize this as a side effect.
  • Using a string key for the visited set ('r,c') but not separating row and column — '12,3' and '1,23' produce the same string. Always use a consistent separator.

Follow-up questions

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

  • Max Area of Island (LC 695) — return the size of the largest island.
  • Number of Enclaves (LC 1020) — islands that can't reach the boundary.
  • How would you solve this if the grid was streaming (too large to fit in memory)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

DFS or BFS?

Both are O(m*n). DFS is shorter to write. BFS avoids deep call stacks on large grids. BFS also doesn't mutate the grid if you use a visited set. Ask the interviewer which they prefer.

Why mark cells '0' during DFS?

It prevents re-visiting the same cell and avoids allocating a separate visited array. The trade-off is mutating the input.

What counts as adjacent?

Only horizontal and vertical neighbors — 4-directional. Not diagonal. The problem statement confirms this.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →