Skip to main content

16. Number of Islands

mediumAsked at DigitalOcean

Count connected components in a grid using BFS/DFS — a staple at DigitalOcean that maps directly to cluster-discovery in network topology.

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

  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'

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. Brute force (no in-place mutation)

Use a visited set and DFS, adding O(m*n) extra memory instead of mutating the grid.

Time
O(m*n)
Space
O(m*n)
// DFS with separate visited set
function numIslands(grid) {
  const visited = new Set();
  let count = 0;
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[0].length; c++)
      if (grid[r][c] === '1' && !visited.has(r+','+c)) {
        dfs(grid, r, c, visited);
        count++;
      }
  return count;
}

Tradeoff:

2. BFS with in-place sink

When we find land, BFS all connected cells and mark them '0' to avoid revisiting. Single pass gives O(m*n) time and O(min(m,n)) queue space.

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') {
        count++;
        const q = [[r, c]];
        grid[r][c] = '0';
        while (q.length) {
          const [row, col] = q.shift();
          for (const [dr, dc] of dirs) {
            const nr = row+dr, nc = col+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:

DigitalOcean-specific tips

DigitalOcean focuses on graph algorithms for network topology — frame your solution around connected-component discovery in data-center subnet graphs to stand out.

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

Practice these live with InterviewChamp.AI →