Skip to main content

21. Number of Islands

mediumAsked at Meta

Count connected land regions in a 2D grid — Meta uses this BFS/DFS pattern directly in social-graph clustering and detecting connected communities in their global friend network.

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

  • 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

Explanation: All the '1's are connected, forming a single island.

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)

Iterate every cell; on finding unvisited land, DFS to mark the whole component visited, incrementing a counter.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  const visited = Array.from({length: m}, () => new Array(n).fill(false));
  let count = 0;
  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] === '0') return;
    visited[r][c] = true;
    dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (!visited[r][c] && grid[r][c] === '1') { count++; dfs(r, c); }
    }
  }
  return count;
}

Tradeoff:

2. Optimal (in-place DFS sink)

Mutate '1' to '0' as you flood-fill to avoid extra visited space. Same O(m*n) time but O(1) auxiliary space (recursion stack aside).

Time
O(m*n)
Space
O(min(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') { count++; dfs(r, c); }
    }
  }
  return count;
}

Tradeoff:

Meta-specific tips

Meta interviewers care about scale: a 300x300 grid is manageable, but they will ask how you would handle a distributed grid sharded across servers — think Union-Find with remote merge. Expect a follow-up about BFS vs DFS trade-offs when the grid is sparse vs dense, and always clarify whether mutating input is acceptable.

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

Practice these live with InterviewChamp.AI →