Skip to main content

21. Number of Islands

mediumAsked at Yelp

Count connected components of '1's in a 2D grid — Yelp uses flood-fill to test whether candidates can scale grid traversal to geo-cell clustering of dense business regions.

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 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"],["1","0","0"],["0","0","1"]]
Output
2

Example 2

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

Approaches

1. Iterative BFS per cell

Walk the grid; when you hit unvisited land, BFS from it and mark visited.

Time
O(mn)
Space
O(mn)
let count = 0;
const seen = new Set();
for (let i = 0; i < grid.length; i++)
  for (let j = 0; j < grid[0].length; j++)
    if (grid[i][j] === '1' && !seen.has(i+','+j)) {
      count++;
      const q = [[i, j]];
      while (q.length) {
        const [r, c] = q.shift();
        if (r<0||c<0||r>=grid.length||c>=grid[0].length||grid[r][c]==='0'||seen.has(r+','+c)) continue;
        seen.add(r+','+c);
        q.push([r+1,c],[r-1,c],[r,c+1],[r,c-1]);
      }
    }
return count;

Tradeoff:

2. DFS flood-fill in place

Walk the grid; on land, recursively sink the whole island to '0' and increment the count.

Time
O(mn)
Space
O(mn)
function numIslands(grid) {
  let count = 0;
  const sink = (r, c) => {
    if (r<0||c<0||r>=grid.length||c>=grid[0].length||grid[r][c]!=='1') return;
    grid[r][c] = '0';
    sink(r+1,c); sink(r-1,c); sink(r,c+1); sink(r,c-1);
  };
  for (let i = 0; i < grid.length; i++)
    for (let j = 0; j < grid[0].length; j++)
      if (grid[i][j] === '1') { count++; sink(i, j); }
  return count;
}

Tradeoff:

Yelp-specific tips

Yelp will pivot to geo indexing — be ready to discuss how island-count generalizes to clustering geohash cells into dense business districts for map-tile pre-rendering.

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

Practice these live with InterviewChamp.AI →