Skip to main content

200. Number of Islands

mediumAsked at HP

HP's imaging and scanning systems detect contiguous regions of ink, toner, or light to distinguish characters and objects on a page. Number of Islands is the archetypal connected-components problem that underlies this region-detection logic — HP uses it to test BFS/DFS grid traversal for systems roles.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2026-Q1)— HP SWE onsite candidates cite Number of Islands as a common medium problem in second and third rounds.
  • Blind (2025-11)— HP interview prep discussions include Number of Islands as a core graph/grid problem for backend and systems roles.

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.

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

Explanation: All land cells are connected — one island.

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

Explanation: Three distinct connected components of land.

Approaches

1. DFS with in-place marking

Iterate every cell. When a '1' is found, increment the island count and DFS-flood-fill all connected land cells by marking them '0' (or '#') to avoid revisiting.

Time
O(m * n)
Space
O(m * n) recursion stack in 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'; // mark visited
    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: Clean and concise. Mutates the input grid — mention this trade-off and offer to use a separate visited matrix if mutation is not allowed.

2. BFS with queue

Same idea but use an explicit queue instead of recursion. Avoids deep call stacks for very large grids.

Time
O(m * n)
Space
O(min(m, n)) queue at any point
function numIslands(grid) {
  let count = 0;
  const m = grid.length, n = grid[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        count++;
        const queue = [[r, c]];
        grid[r][c] = '0';
        while (queue.length) {
          const [cr, cc] = queue.shift();
          for (const [dr, dc] of dirs) {
            const nr = cr + dr, nc = cc + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === '1') {
              grid[nr][nc] = '0';
              queue.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return count;
}

Tradeoff: Avoids recursion stack overflow. HP systems engineers prefer BFS for large grids where deep DFS could blow the call stack.

HP-specific tips

HP systems interviewers often ask whether you'd mutate the input or use a separate visited matrix — discuss both options. For large grids (HP's imaging grids can be millions of pixels), BFS with an explicit queue is safer than recursive DFS due to stack-depth limits. Mention Union-Find as an alternative if asked about a streaming or incremental island-detection scenario.

Common mistakes

  • Not marking cells as visited before adding them to the BFS queue — causes duplicate processing and overcounting.
  • Forgetting boundary checks — always verify 0 <= r < m and 0 <= c < n before accessing grid[r][c].
  • Marking cells as visited after popping from the queue instead of before pushing — allows the same cell to be pushed multiple times.
  • Using diagonal adjacency instead of 4-directional — the problem specifies horizontal/vertical only.

Follow-up questions

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

  • Count the area (number of cells) of the largest island (LC 695).
  • How would you solve this with Union-Find for an incremental 'add land' operation?
  • What if the grid wraps around at the edges (toroidal grid)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Is it safe to mutate the input grid?

In an interview, ask first. If mutation is not allowed, use a separate boolean visited[][] array of the same dimensions. Either approach is O(m*n) space.

What is the worst-case recursion depth for DFS?

If the entire grid is one island, DFS can recurse m*n levels deep. For a 300×300 grid that's 90,000 frames — likely to overflow the call stack. BFS is safer.

Why is BFS queue size O(min(m, n)) and not O(m*n)?

The BFS frontier expands layer by layer. The maximum frontier size at any BFS level is bounded by the shorter dimension (the perimeter of the BFS wavefront), not the total grid size.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →