Skip to main content

15. Number of Islands

mediumAsked at Tesla

Count connected land regions in a grid — Tesla uses BFS/DFS grid traversal to reason about how onboard cameras segment obstacle maps and identify distinct occupancy zones during Autopilot scene reconstruction.

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

Problem

Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically.

Constraints

  • 1 <= grid.length, grid[0].length <= 300
  • grid[i][j] is '0' or '1'
  • Grid cells outside bounds are treated as water

Examples

Example 1

Input
grid = [["1","1","0"],["0","1","0"],["0","0","1"]]
Output
2

Explanation: Top-left cluster and the single bottom-right cell form two separate islands.

Example 2

Input
grid = [["1","1","1"],["0","1","0"],["1","0","1"]]
Output
3

Approaches

1. Brute force BFS with visited set

Scan every cell; when a '1' is found that hasn't been visited, run BFS to mark all connected cells, incrementing an island counter.

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;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1' && !visited[r][c]) {
        count++;
        const queue = [[r, c]];
        visited[r][c] = true;
        while (queue.length) {
          const [cr, cc] = queue.shift();
          for (const [dr, dc] of dirs) {
            const nr = cr + dr, nc = cc + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                grid[nr][nc] === '1' && !visited[nr][nc]) {
              visited[nr][nc] = true;
              queue.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

2. In-place DFS (mutating grid)

Flood-fill each unvisited land cell to '0' via DFS, avoiding extra space for a visited matrix. Preferred when mutating input is acceptable.

Time
O(m*n)
Space
O(m*n) recursion stack worst case
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';
    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:

Tesla-specific tips

Tesla interviewers care less about which traversal you choose and more about how you articulate the connectivity model — they draw parallels to obstacle-map segmentation in FSD. State upfront whether you're mutating the input and why; in safety-critical sensor pipelines, preserving original data matters. Discuss how you'd scale this to sparse maps where only 5% of cells are land.

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

Practice these live with InterviewChamp.AI →