Skip to main content

70. Number of Islands

mediumAsked at Reddit

Count the number of connected components of 1s in a grid. Reddit uses this DFS/BFS classic to test grid traversal — the same shape used when clustering coordinated abuse cells in their fraud-detection IP-grid.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit trust-and-safety phone screen — fraud-cluster detection.
  • Blind (2025-12)— Reported as Reddit infra-team standard.

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 is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

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

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

For each '1' not yet visited, DFS the connected component; track visited in a separate set.

Time
O(m*n)
Space
O(m*n)
// Same idea as the in-place version, but uses an extra Set.

Tradeoff: Works. O(m*n) extra space.

2. DFS with in-place mark (optimal)

When you find a '1', DFS and overwrite to '0' (or '2') to mark visited. Each component increments the count.

Time
O(m*n)
Space
O(m*n) recursion worst case
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  function dfs(i, j) {
    if (i<0||i>=m||j<0||j>=n||grid[i][j]!=='1') return;
    grid[i][j] = '0';
    dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1);
  }
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) {
    if (grid[i][j] === '1') { count++; dfs(i, j); }
  }
  return count;
}

Tradeoff: In-place mark saves memory. Mutation of input is acceptable here.

Reddit-specific tips

Reddit interviewers want you to discuss the trade-off: in-place mark vs. visited set. Bonus signal: mention Union-Find as an alternative useful when you need to merge clusters incrementally — same problem shape as their abuse-IP cluster detection.

Common mistakes

  • Forgetting one of the four directions.
  • Stack-overflow on huge grids (use BFS instead).
  • Counting cells instead of components.

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Number of islands II (LC 305) — dynamic with Union-Find.
  • Max area of island (LC 695).
  • Surrounded regions (LC 130).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

DFS or BFS?

Either works. DFS is cleaner code; BFS avoids stack overflow on 300x300 grids of all 1s.

Union-Find when?

When islands grow incrementally (LC 305) or when you need to query connectivity efficiently.

Practice these live with InterviewChamp.AI

Drill Number of Islands and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →