Skip to main content

200. Number of Islands

mediumAsked at Gusto

Count the number of islands in a grid. Gusto uses this to introduce graph traversal in a 2D setting — they want to see BFS or DFS with in-place marking, and to hear you articulate why each approach is equivalent before choosing one.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2025-11)— Reported in Gusto SWE onsite feedback as a graph-traversal medium with a follow-up on Union-Find.
  • Blind (2025-09)— Gusto threads mention Number of Islands as a reliable BFS/DFS check in mid-level engineering interviews.

Problem

Given an m×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

Explanation: All connected land cells form 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 separate connected components of land.

Approaches

1. DFS with in-place marking

Iterate every cell. When a '1' is found, increment the count and DFS to mark all reachable connected land as visited (set to '0' or a sentinel).

Time
O(m × n)
Space
O(m × n) for recursion stack in worst case
function numIslands(grid) {
  let count = 0;
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(grid, r, c);
      }
    }
  }
  return count;
}
function dfs(grid, r, c) {
  if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] !== '1') return;
  grid[r][c] = '0'; // mark visited
  dfs(grid, r + 1, c);
  dfs(grid, r - 1, c);
  dfs(grid, r, c + 1);
  dfs(grid, r, c - 1);
}

Tradeoff: Simple and concise. In-place marking avoids a visited array. Recursion stack can reach O(m×n) for a fully-land grid — mention this and offer BFS if stack overflow is a concern.

2. BFS with a queue

Same outer loop. When a '1' is found, use a queue-based BFS to mark all connected land, eliminating deep recursion.

Time
O(m × n)
Space
O(min(m, n)) for the BFS queue
function numIslands(grid) {
  let count = 0;
  const rows = grid.length, cols = grid[0].length;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        grid[r][c] = '0';
        const queue = [[r, c]];
        while (queue.length) {
          const [cr, cc] = queue.shift();
          for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
            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: Avoids stack overflow risk on large all-land grids. Queue space is bounded by the perimeter of the BFS frontier, not the full grid size. Preferred when robustness matters.

Gusto-specific tips

Gusto interviewers appreciate candidates who proactively flag the mutating-the-input tradeoff: in-place marking is efficient but destructive. Offer to use a visited Set or restore the grid afterwards if mutation is unacceptable. Also mention that the BFS approach avoids stack overflow for very large grids — this shows systems-level thinking they value.

Common mistakes

  • Not marking cells as visited before adding to the BFS queue — causes the same cell to be enqueued multiple times.
  • Checking bounds after the recursive call instead of before — leads to array-out-of-bounds errors.
  • Counting '0' cells or missing the increment before the DFS/BFS call.
  • Using a 2D visited array but still processing already-visited '0' cells — wastes time.

Follow-up questions

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

  • Max Area of Island (LC 695) — return the size of the largest island.
  • Number of Distinct Islands (LC 694) — count islands with distinct shapes.
  • How would you solve this with Union-Find?

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 diagonal connectivity considered?

No — only horizontal and vertical adjacency counts. The four-direction array [[1,0],[-1,0],[0,1],[0,-1]] captures this exactly.

Is it acceptable to mutate the input grid?

Typically yes in interviews — mention the tradeoff. If the grid must be preserved, use a separate visited boolean array or Set.

What is the BFS queue's maximum size?

In the worst case (a large filled square), it's O(min(m,n)) — bounded by the perimeter of the expanding frontier, not the full island area.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →