Skip to main content

200. Number of Islands

mediumAsked at Snap

Snap's AR segmentation detects connected regions of similar pixels to isolate faces and objects — number of islands is the graph-traversal core of that pipeline.

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

Problem

Given an m x n 2D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

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. Brute force BFS per cell

For each unvisited '1', do a BFS/DFS and mark visited cells in a separate boolean grid. O(m*n) space for the visited array.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  const visited = Array.from({ length: m }, () => new Array(n).fill(false));
  let count = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  function bfs(r, c) {
    const queue = [[r, c]];
    visited[r][c] = true;
    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 && !visited[nr][nc] && grid[nr][nc] === '1') {
          visited[nr][nc] = true;
          queue.push([nr, nc]);
        }
      }
    }
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (!visited[r][c] && grid[r][c] === '1') {
        bfs(r, c);
        count++;
      }
    }
  }
  return count;
}

Tradeoff:

2. In-place DFS (sink visited land)

Mutate grid directly — mark visited '1' cells as '0' during DFS to avoid a separate visited array. Same time complexity, O(1) extra space (recursion stack is O(m*n) worst case but avoids heap allocation).

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

Tradeoff:

Snap-specific tips

Snap often asks this as a canvas-segmentation framing: 'You have a binary mask from the AR pipeline — how many disconnected foreground regions exist?' Mention that you'd prefer BFS in prod to avoid call-stack overflow on large masks.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →