Skip to main content

22. Number of Islands

easyAsked at Spotify

Count connected components in a 2-D grid using BFS/DFS — a graph traversal warm-up that Spotify applies to connected-artist clustering in recommendation graphs.

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 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. DFS sink-and-count

For each unvisited '1', increment the island count and flood-fill (DFS) all connected cells to '0' so they aren't counted again.

Time
O(m * n)
Space
O(m * n) recursion stack
function numIslands(grid) {
  let count = 0;
  const 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:

2. BFS iterative

Same logic but uses an explicit queue instead of recursion — avoids stack overflow on very large grids, a concern for production-scale adjacency data.

Time
O(m * n)
Space
O(min(m, n)) queue
function numIslands(grid) {
  let count = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] !== '1') continue;
      count++;
      const q = [[r, c]];
      grid[r][c] = '0';
      while (q.length) {
        const [cr, cc] = q.shift();
        for (const [dr, dc] of dirs) {
          const nr = cr + dr, nc = cc + dc;
          if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            q.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

Spotify-specific tips

Spotify uses graph traversal extensively for artist-relationship graphs — think genre clusters or collaboration networks. Mention that the BFS approach maps cleanly to breadth-first exploration of artist neighbors in an adjacency list, and that flood-fill is equivalent to marking visited nodes to avoid processing the same artist twice in a recommendation pass.

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

Practice these live with InterviewChamp.AI →