Skip to main content

25. Number of Islands

mediumAsked at Databricks

Count connected land components in a 2-D grid — a BFS/DFS connected-components pattern Databricks extends to counting disconnected data-lake zones and partitioning graph-based cluster topology.

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

Problem

Given an m x n 2-D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and formed by connecting adjacent land cells 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. DFS flood-fill

Iterate every cell. On encountering an unvisited '1', increment the island count and DFS-flood all connected land cells, marking them visited by overwriting with '0'.

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';
    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:

2. BFS iterative

Same traversal but using an explicit queue instead of recursion, avoiding call-stack overflow on large grids — important for production-scale grid data.

Time
O(m * n)
Space
O(min(m, n)) queue
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  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++;
      grid[r][c] = '0';
      const queue = [[r, c]];
      while (queue.length > 0) {
        const [cr, cc] = queue.shift();
        for (const [dr, dc] of dirs) {
          const nr = cr + dr, nc = cc + 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:

Databricks-specific tips

Databricks often asks this with a follow-up: 'How would you solve this on a distributed grid too large to fit on one machine?' The answer requires Union-Find with cross-partition boundary stitching — the same technique Databricks's graph analytics library GraphX uses. Volunteer that extension unprompted; it shows you think beyond in-memory constraints, which is the entire Databricks world-view.

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

Practice these live with InterviewChamp.AI →