Skip to main content

200. Number of Islands

mediumAsked at eBay

eBay's geo-search team segments geographic regions — think grouping contiguous postal codes into delivery zones. Number of Islands is the graph-traversal foundation: count connected components in a grid. eBay interviewers use it to test BFS vs. DFS choice, visited-state management, and whether you can handle a 2D graph without a separate visited matrix.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2026-Q1)— Reported as one of the most common eBay medium problems in onsite rounds, often testing BFS/DFS graph traversal.
  • Blind (2025-12)— eBay SWE threads consistently list Number of Islands as a core medium problem; candidates report both BFS and DFS solutions being accepted.

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 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","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 into 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 cells.

Approaches

1. DFS with in-place marking

Iterate every cell. When a '1' is found, increment count and DFS to mark all connected land cells as '0' (visited). No separate visited matrix needed.

Time
O(m * n)
Space
O(m * n) call stack in worst case
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  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: O(mn) time. O(mn) call stack in the worst case (entire grid is one island). Clean and concise — the preferred answer for most eBay interviews. Mention that mutating the input avoids a separate visited matrix.

2. BFS with queue

Same outer loop; when a '1' is found, use a queue to BFS all connected land cells. Mark as '0' when enqueuing to prevent re-visits.

Time
O(m * n)
Space
O(min(m, n)) queue in typical case
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  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 > 0) {
          const [row, col] = queue.shift();
          for (const [dr, dc] of dirs) {
            const nr = row + dr, nc = col + 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: O(mn) time. BFS avoids the call-stack overflow risk for very large islands. Preferred when grid dimensions approach the 300×300 constraint and stack depth is a concern.

eBay-specific tips

eBay interviewers ask the trade-off between DFS and BFS: 'DFS is simpler to code but risks stack overflow on huge grids (300×300 = 90,000 deep). BFS uses an explicit queue and avoids that.' Also address the mutation trade-off: 'I'm marking '1' as '0' in-place — if the caller needs the original grid, I should restore it or use a separate visited Set.' For the 'millions of concurrent buyers' follow-up: 'At extreme scale this would be a distributed graph problem — but for 300×300, in-place DFS is fine.'

Common mistakes

  • Not marking the starting cell as '0' before BFS/DFS — causes infinite loops when the cell's neighbors push it back onto the queue.
  • Marking visited on dequeue instead of on enqueue in BFS — cells get enqueued multiple times, leading to incorrect counts.
  • Missing boundary checks — always check r >= 0, r < m, c >= 0, c < n before accessing grid[r][c].
  • Diagonal connectivity — the problem specifies horizontal/vertical only; don't add diagonal directions.

Follow-up questions

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

  • Max Area of Island (LC 695) — return the size of the largest island instead of a count.
  • Number of Enclaves (LC 1020) — islands that can't reach the border.
  • How would you solve this with Union-Find (Disjoint Set Union) instead of DFS/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

Why mark cells as '0' instead of using a separate visited array?

It saves O(mn) space. If the caller requires the original grid to be unchanged, you'd need to restore mutated cells after DFS or use a separate boolean matrix.

Can DFS stack-overflow on a 300×300 grid?

Theoretically yes — if the entire 90,000-cell grid is one island, DFS recurses 90,000 levels deep. In practice, JavaScript's default call stack can handle a few thousand levels safely. BFS is the safe choice for maximum grid sizes.

How does Union-Find compare to DFS/BFS for this problem?

Union-Find works in near-O(mn) time using path compression. It's more complex to implement but shines in problems where you repeatedly merge components or query connectivity dynamically.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →