Skip to main content

22. Number of Islands

mediumAsked at PayPal

Count the number of islands (connected components of '1's) in a binary grid. PayPal uses this BFS/DFS grid traversal problem to test graph connectivity reasoning — directly applicable to fraud ring detection where connected transaction nodes form suspect clusters.

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

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • Glassdoor (2026)— PayPal SWE L4 reported grid connectivity problem as main coding question in onsite
  • Blind (2025)— PayPal interview prep threads consistently list Number of Islands as a top medium asked

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

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. BFS flood fill

Scan every cell; when an unvisited '1' is found, increment count and BFS to mark all connected land cells as visited.

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

Tradeoff: Mutates the grid in place (mark visited as '0'). Mention this trade-off and offer to use a separate visited array if the input must be preserved.

2. DFS recursive flood fill

Same idea with recursive DFS — cleaner code but uses call-stack space proportional to island size. For very large grids (300×300) the iterative BFS is safer against stack overflow, but DFS is idiomatic and faster to write under time pressure.

Time
O(m*n)
Space
O(m*n) worst case for call stack
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 i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '1') {
        count++;
        dfs(i, j);
      }
    }
  }
  return count;
}

Tradeoff: Elegant and fast to write — preferred in interviews. At PayPal, frame as 'connected fraud-ring detection': each island is a cluster of related suspicious transactions.

PayPal-specific tips

PayPal interviews focus on payment processing, fraud detection logic, financial reconciliation algorithms, and distributed transaction design. Hash maps, sliding windows, and two-pointer techniques appear frequently.

Common mistakes

  • Forgetting to mark cells as visited before adding to the BFS queue, causing the same cell to be enqueued multiple times
  • Using grid[r][c] = '0' after dequeuing instead of before enqueuing — cells are visited multiple times
  • Off-by-one in boundary checks — use `r >= 0 && r < m && c >= 0 && c < n`

Follow-up questions

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

  • Max area of an island — return the size of the largest island (LC 695)
  • Number of islands in a stream — grid is updated dynamically, use Union-Find (LC 305)
  • Count connected components where components are defined by diagonal adjacency as well

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Can I use Union-Find instead of DFS/BFS?

Yes — Union-Find works well and is preferred for the streaming variant (LC 305) where cells are added one at a time. For the static problem DFS/BFS is simpler and equally correct.

Is it okay to modify the input grid?

Ask the interviewer. Modifying in place is O(1) extra space but destructive. If the grid must be preserved, use a boolean visited array or a Set of 'r,c' strings.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →