Skip to main content

15. Number of Islands

mediumAsked at Roblox

Count connected land regions in a binary grid — Roblox uses this pattern to identify distinct terrain chunks when generating and streaming open-world maps to millions of concurrent players.

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 land cell, launch a BFS to mark the entire island as visited, then increment the count.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let count = 0;

  function bfs(r, c) {
    const queue = [[r, c]];
    visited[r][c] = true;
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    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 < rows && nc >= 0 && nc < cols && !visited[nr][nc] && grid[nr][nc] === '1') {
          visited[nr][nc] = true;
          queue.push([nr, nc]);
        }
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1' && !visited[r][c]) {
        bfs(r, c);
        count++;
      }
    }
  }
  return count;
}

Tradeoff:

2. Optimal — DFS with in-place sink

DFS from each unvisited '1' cell, marking visited cells as '0' in-place to avoid a separate visited array. Same time complexity with lower constant overhead.

Time
O(m*n)
Space
O(m*n) call stack worst case
function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '0';
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        dfs(r, c);
        count++;
      }
    }
  }
  return count;
}

Tradeoff:

Roblox-specific tips

Roblox interviewers care about how you handle large grids at scale — think millions of tiles in a streamed world. They'll ask whether you'd prefer iterative BFS over recursive DFS for stack-overflow safety, and how you'd parallelize island counting across map shards. Mention Union-Find as a natural extension if they ask about dynamic land updates.

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 Roblox interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →