Skip to main content

200. Number of Islands

mediumAsked at GoDaddy

Count connected land masses in a binary grid using BFS or DFS — GoDaddy's network team models hosting-cluster topology as a grid and uses this pattern to identify isolated server groups during infrastructure partitioning reviews.

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 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 with in-place marking

For each unvisited '1', increment the island count and DFS-flood-fill all connected cells to '0' to avoid revisiting.

Time
O(m * n)
Space
O(m * n) call stack
function numIslands(grid) {
  let count = 0;
  const rows = grid.length;
  const cols = grid[0].length;
  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || 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 < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff:

2. BFS with queue

Same flood-fill logic using an explicit queue; avoids deep recursion stack on large grids.

Time
O(m * n)
Space
O(min(m, n)) queue width
function numIslands(grid) {
  let count = 0;
  const rows = grid.length;
  const cols = grid[0].length;
  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') {
        count++;
        const queue = [[r, c]];
        grid[r][c] = '0';
        let qi = 0;
        while (qi < queue.length) {
          const [cr, cc] = queue[qi++];
          for (const [dr, dc] of dirs) {
            const nr = cr + dr;
            const nc = cc + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
              grid[nr][nc] = '0';
              queue.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

GoDaddy-specific tips

GoDaddy network engineers ask this to see if you immediately spot the flood-fill sub-problem and discuss which traversal fits the grid's aspect ratio — BFS is preferred when rows * cols can exhaust the call stack. Mentioning Union-Find as a third option signals strong algorithm breadth.

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

Practice these live with InterviewChamp.AI →