18. Number of Islands

mediumAsked at Activision

Count connected land regions in a 2D grid — Activision uses this to gauge BFS/DFS flood-fill instincts before anti-cheat cluster-detection problems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Given an m x n grid 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

Example 2

Input

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

Output

Approaches

1. Union-Find

Union each land cell with neighboring land; count distinct roots.

Time: O(mn * alpha(mn))
Space: O(mn)

// DSU with path compression — works but DFS flood-fill is simpler here

Tradeoff:

2. DFS flood fill

Scan grid; when you hit unvisited land, DFS to mark the whole island and increment the counter.

Time: O(mn)
Space: O(mn)

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

Tradeoff:

Activision-specific tips

Activision likes when you note that mutating the input is acceptable here — same shape they use when clustering anti-cheat telemetry pings into suspect cohorts.

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

Practice these live with InterviewChamp.AI →