Skip to main content

19. Number of Islands

mediumAsked at Indeed

Count connected land regions in a grid — Indeed uses this pattern to identify clusters of related job listings in geographic heat-map generation.

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","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. BFS flood fill

For every unvisited '1', BFS-flood the connected region, marking cells visited.

Time
O(m*n)
Space
O(min(m,n))
function numIslands(grid) {
  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') { bfs(grid, r, c); count++; }
    }
  }
  return count;
}
function bfs(grid, r, c) {
  const q = [[r, c]];
  grid[r][c] = '0';
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  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]);
      }
    }
  }
}

Tradeoff:

2. DFS in-place marking

Recursively mark connected cells as visited ('0') in place to avoid extra space from a visited array.

Time
O(m*n)
Space
O(m*n) recursion stack
function numIslands(grid) {
  let count = 0;
  function 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') { dfs(r, c); count++; }
  return count;
}

Tradeoff:

Indeed-specific tips

Indeed uses DFS/BFS grid problems to assess spatial reasoning; note whether mutating the input is acceptable before coding and ask about large grid memory constraints.

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

Practice these live with InterviewChamp.AI →