Skip to main content

17. Number of Islands

mediumAsked at ServiceNow

Count connected components of '1's in a 2-D grid using DFS or BFS. ServiceNow asks this to test graph traversal reasoning — the same connected-component logic powers their CMDB relationship discovery, where service clusters must be identified from a dependency grid.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • LeetCode Discuss (2026)— Flagged as a ServiceNow SDE-II onsite staple for graph/BFS questions.
  • Glassdoor (2025)— Reported in ServiceNow mid-level engineering interviews.

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

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 without in-place marking

Use a separate visited set and DFS from every unvisited '1' cell.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  const visited = new Set();
  let count = 0;
  function dfs(r, c) {
    const key = r + ',' + c;
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
        || grid[r][c] === '0' || visited.has(key)) return;
    visited.add(key);
    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' && !visited.has(r+','+c)) { dfs(r,c); count++; }
  return count;
}

Tradeoff: Correct but allocates a large Set and uses string keys — string concatenation is slow and memory-heavy. In-place marking is preferred.

2. In-place DFS with sink marking

When entering a '1' cell, immediately set it to '0' (sink it) to prevent revisiting. No auxiliary visited structure needed. Increment the island counter once per unvisited land cell. Restore the grid afterwards if mutation is not allowed.

Time
O(m*n)
Space
O(m*n) recursion stack worst case
function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // sink
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff: Optimal time and space (no extra visited structure). Mention to ServiceNow interviewers whether mutation is acceptable — if not, copy the grid first or use BFS with a queue and a separate set.

ServiceNow-specific tips

ServiceNow interviewers want you to explicitly discuss whether you can mutate the input grid, because in their CMDB discovery context the grid represents live configuration data that must not be altered. State the tradeoff up front: mutate for O(1) space overhead, or copy the grid for safety. Bonus signal: mention Union-Find as an alternative that scales to streaming updates.

Common mistakes

  • Not sinking '1' to '0' immediately on entry — causes the DFS to revisit cells and double-count islands.
  • Forgetting bounds checks before the grid[r][c] check — throws index-out-of-bounds on edge cells.
  • Counting islands inside the DFS instead of the outer loop — counts one per cell rather than one per connected component.

Follow-up questions

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

  • Number of islands II: dynamic grid with addLand operations — use Union-Find.
  • Max area of an island (LC 695): track size during DFS.
  • Surrounded regions: flip 'O' regions not connected to the border to 'X' (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 — which should I use?

Either works. DFS is shorter to write. BFS avoids recursion stack overflow on large grids (300x300 = 90,000 cells, which could blow the stack). Mention iterative BFS as the production-safe choice.

Can I use Union-Find instead?

Yes — Union-Find is ideal if the grid changes dynamically (Number of Islands II). For a static grid, DFS/BFS is simpler. Mentioning Union-Find shows breadth and is a strong bonus signal at ServiceNow.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →