Skip to main content

26. Number of Islands

mediumAsked at Apple

Count connected land regions in a binary grid using BFS/DFS — Apple applies this grid-traversal pattern to UI layout engines that must identify distinct content regions on a display, and to Maps clustering connected geographic tiles.

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

Problem

Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (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'
  • Islands are connected 4-directionally (no diagonals)

Examples

Example 1

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

Example 2

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

Approaches

1. DFS (recursive sink)

For each unvisited '1', increment count and DFS to mark all connected land as '0'. No extra visited set needed if mutating the grid is allowed.

Time
O(m*n)
Space
O(m*n)
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)

Use a queue to spread from each unvisited land cell. Avoids deep recursion stack overflow on large grids — important in memory-constrained iOS devices.

Time
O(m*n)
Space
O(min(m,n))
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++;
      grid[r][c] = '0';
      const queue = [[r, c]];
      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 < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

Apple-specific tips

Apple Maps and the Spatial Computing team deal with connected-region problems constantly — mention that BFS is preferred over DFS in production because it avoids call-stack overflow on large grid inputs, which matters on Apple Watch with its constrained stack. Interviewers will ask whether you need to restore the grid after mutation; have an answer ready (clone or use a visited Set). Union-Find is an elegant follow-up Apple sometimes asks for — practice it if you have time.

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

Practice these live with InterviewChamp.AI →