Skip to main content

81. Number of Islands

mediumAsked at Datadog

Count connected components of '1's in a 2D grid. Datadog uses this as the canonical grid-BFS/DFS question — same shape as counting active service clusters in a service-mesh observability view.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — service-cluster analog.
  • Blind (2025-12)— Recurring Datadog problem.

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. BFS with visited matrix

For each unvisited '1', BFS marking all connected '1's visited; increment count.

Time
O(m * n)
Space
O(m * n)
// Standard BFS with a visited[][] array.

Tradeoff: Works but allocates visited. Datadog accepts in-place marking too.

2. DFS with in-place mark (optimal)

For each '1', recursively flood-fill setting to '0'; each flood = one island.

Time
O(m * n)
Space
O(m * n) recursion worst case
function numIslands(grid) {
  let count = 0;
  const m = grid.length, n = grid[0].length;
  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || 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: In-place marking — no extra memory beyond recursion. Datadog-canonical.

Datadog-specific tips

Datadog will follow up with: 'Now do this on a streaming grid where cells become 1 over time' (LC 305) — that's Union-Find. Mention Union-Find as the streaming variant; this baseline question is just to verify you can flood-fill.

Common mistakes

  • Using a Set of (r,c) strings for visited — slower than in-place marking.
  • Forgetting the bounds check inside dfs — easier to put it in dfs than in the caller.
  • Checking '1' as a number — it's a string in this problem ('0' or '1').

Follow-up questions

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

  • Number of Islands II (LC 305) — streaming, Union-Find.
  • Max Area of Island (LC 695) — return largest size.
  • Datadog-style: count active service clusters via flood-fill on connectivity graph.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

BFS or DFS?

Both work. DFS is shorter to write; BFS is safer for huge islands (avoids deep recursion). Datadog accepts either.

Why mark in place?

Saves the visited matrix. If the input must be preserved, allocate visited[][].

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →