Skip to main content

19. Number of Islands

mediumAsked at Expedia

Count connected land masses in a grid — Expedia applies the same BFS/DFS region-counting logic when clustering geographically adjacent hotel markets into a single search region.

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 land cells 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","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output
3

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. Brute force DFS with visited set

Scan every cell; on finding an unvisited '1', launch DFS marking cells in a separate visited set.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  const visited = new Set();
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (grid[r][c] === '0' || visited.has(`${r},${c}`)) return;
    visited.add(`${r},${c}`);
    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' && !visited.has(`${r},${c}`)) {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff:

2. In-place DFS sink

Mutate the grid — overwrite visited land cells with '0' so no visited set is needed. Halves auxiliary space.

Time
O(m*n)
Space
O(m*n) call stack, O(1) extra
function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;

  function sink(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || 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 r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        sink(r, c);
      }
    }
  }
  return count;
}

Tradeoff:

Expedia-specific tips

Expedia interviewers want to see you articulate the two traversal strategies and then pick the in-place sink variant — they care about minimizing auxiliary allocations inside tight search-loop hot paths. Mention Union-Find as a natural scale-out for distributed market clustering if time allows.

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

Practice these live with InterviewChamp.AI →