Skip to main content

200. Number of Islands

mediumAsked at HubSpot

HubSpot asks Number of Islands to test graph traversal fundamentals — BFS and DFS on an implicit grid — skills that transfer to connected-component analysis in their contact relationship graph and account hierarchy features.

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

Source citations

Public interview reports confirming this problem appears in HubSpot loops.

  • Glassdoor (2026-Q1)— HubSpot SWE onsite reports consistently mention Number of Islands as a core graph traversal problem.
  • Blind (2025-11)— Multiple HubSpot interview threads list Number of Islands as a high-signal medium for BFS/DFS proficiency.

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","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output
3

Explanation: Three connected components of '1's.

Example 2

Input
grid = [["1","1","1"],["0","1","0"],["1","1","1"]]
Output
1

Explanation: All '1's are connected (directly or indirectly), forming one island.

Approaches

1. DFS with in-place marking

Iterate over every cell. When a '1' is found, increment the island count and run DFS to mark all connected '1's as visited by setting them to '0'. After DFS, all cells in that island are sunk.

Time
O(m * n)
Space
O(m * n) worst-case recursion stack
function numIslands(grid) {
  let count = 0;
  const rows = grid.length, cols = grid[0].length;
  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || 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 < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff: O(m*n) time and space. In-place marking avoids a separate visited array. The recursion stack depth can be O(m*n) for a fully-land grid — mention this and offer BFS as a stack-overflow-safe alternative.

2. BFS with queue

Same outer iteration. When a '1' is found, increment count and use a queue to perform BFS, marking each neighbor '0' as it's enqueued to prevent duplicate processing.

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

Tradeoff: BFS avoids deep recursion stacks for large grids. Queue space is bounded by the perimeter of the island (~O(min(m,n)) in practice). Preferred when the grid could be 300×300 and deep recursion is a concern.

HubSpot-specific tips

State the approach before coding: 'I'll iterate over all cells and run DFS from every unvisited land cell, incrementing a counter and marking visited cells.' HubSpot interviewers will ask about the space complexity of DFS — mention the recursion stack risk and offer BFS. They also probe whether modifying the input is acceptable; offer to use a separate visited set if not. The four-direction array pattern (dirs = [[1,0],[-1,0],[0,1],[0,-1]]) is cleaner than four explicit recursive calls.

Common mistakes

  • Forgetting to mark cells as visited before adding to the queue — causes duplicate processing and overcounting.
  • Not handling the bounds check before accessing grid[r][c] — leads to index-out-of-bounds errors.
  • Using a separate visited array but checking grid[r][c] === '1' again inside DFS — inconsistent visited tracking.
  • Not considering diagonal connections (the problem says horizontal/vertical only — don't add diagonal directions).

Follow-up questions

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

  • Max Area of Island (LC 695) — return the maximum island size instead of island count.
  • Surrounded Regions (LC 130) — capture surrounded '0' regions.
  • How would you solve this if the grid is too large to fit in memory (streaming/distributed approach)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Does modifying the grid in place cause problems?

If the caller needs the grid unchanged, use a separate boolean visited array. In an interview, ask — modifying in place is acceptable and saves O(m*n) space.

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

In BFS, only the current frontier (perimeter of the expanding island) is in the queue at any time. The perimeter of a blob of area A is O(√A), bounded by O(min(m,n)) for grid shapes.

What if grid is empty?

The outer loops don't execute and count = 0 is returned — correctly handled without special-casing.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →