Skip to main content

70. Number of Islands

mediumAsked at Workday

Count the number of islands in a 2D grid of '1' (land) and '0' (water). Workday uses this for grid-DFS counting — same shape as counting connected groups of co-located employees on a floor plan.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE2 onsite — graph DFS staple.
  • Blind (2025)— Workday Pleasanton phone screen.

Problem

Given an m x n 2D binary grid 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.

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. Union-Find

Initialize each '1' as its own set. Union with each '1' neighbor.

Time
O(m*n * α)
Space
O(m*n)
// DSU approach — works but heavier setup

Tradeoff: Equivalent complexity, more code than DFS.

2. DFS flood-fill in place

Scan grid. On '1', increment count, run DFS marking all connected '1's to '#'.

Time
O(m*n)
Space
O(m*n) recursion stack 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] = '#';
    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 marking via '#' saves the visited matrix. Simple and fast.

Workday-specific tips

Workday wants the in-place mark approach. Articulate that overwriting '1' to '#' (or any non-'1' value) is the visited-set substitute. BFS is equivalent — mention it if asked about stack depth.

Common mistakes

  • Forgetting to mark visited — DFS recurses infinitely.
  • Using a separate visited matrix — works but wastes O(m*n) memory.
  • Counting AFTER DFS — count++ should come at the trigger before recursion.

Follow-up questions

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

  • Max Area of Island (LC 695).
  • Number of Distinct Islands (LC 694) — shape canonicalization.
  • Islands and Treasure (LC 286) — multi-source BFS.

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; BFS avoids deep recursion stacks. For 300x300 grids, DFS recursion is fine.

Mutating input — safe?

Ask. If forbidden, use a visited matrix. If allowed, in-place is faster and saves memory.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →