Skip to main content

16. Number of Islands

mediumAsked at Palantir

Given a 2D grid of '1's (land) and '0's (water), count the number of islands. Palantir asks this to verify you write iterative flood-fill cleanly — the same connected-components primitive their entity-resolution pipelines use to cluster duplicate records into a single canonical entity in the ontology.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2026-Q1)— Palantir FDE on-site — followed by 'now do it without recursion'.
  • Blind (2025-09)— Reported with 'entity resolution' framing in the follow-up.
  • LeetCode Discuss (2026-02)— Tagged as Palantir's most common medium.

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'],['1','0','0'],['0','0','1']]
Output
2

Explanation: One island in the top-left, one in the bottom-right.

Example 2

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

Explanation: All land cells are connected through the middle column.

Approaches

1. Recursive DFS flood-fill

Iterate every cell; when you find a '1', DFS-mark the whole island as visited and increment the counter.

Time
O(m*n)
Space
O(m*n) recursion 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 || c < 0 || r >= m || c >= n || grid[r][c] !== '1') return;
    grid[r][c] = '0';
    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 but risks stack overflow on a 300x300 all-land grid (90k recursive frames). Palantir interviewers will probe this.

2. Iterative BFS with queue

Same shape, but use an explicit queue so state lives on the heap. Mark visited inline.

Time
O(m*n)
Space
O(min(m,n)) for the BFS frontier
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  let count = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] !== '1') continue;
      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 && nc >= 0 && nr < m && nc < n && grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

Tradeoff: Same time, safer on large grids. The frontier is bounded by min(m,n) for BFS. Mark visited when ENQUEUING, not when dequeuing, to avoid double-counting.

Palantir-specific tips

Palantir absolutely wants the iterative BFS version — they will explicitly ask 'what if the grid is too deep for recursion'. The other senior signal is connecting this back to entity resolution: each connected component is a cluster of duplicate records that resolve to one canonical entity. Mention Union-Find as the alternative when the problem is dynamic (cells added over time) — they may pivot to that follow-up.

Common mistakes

  • Marking visited on dequeue instead of enqueue — same cell ends up in the queue multiple times, blowing up complexity.
  • Forgetting to handle the '1' as a STRING, not a number — strict equality matters.
  • Mutating the input grid without noting it — Palantir sometimes requires a separate visited set.

Follow-up questions

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

  • Diagonal connections also count (8-direction flood).
  • Number of distinct island shapes (LC 694) — hash the relative coordinates.
  • Online version: cells flip from water to land — use Union-Find with path compression (LC 305).

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 is BFS preferred over DFS here at Palantir?

Because Foundry processes grids that can be enormous (raster data, geospatial layers), and recursive DFS will stack-overflow. BFS keeps state on the heap, which scales to any grid size.

Can I use Union-Find instead?

Yes — initialize each '1' cell as its own set, then union with neighbor '1' cells. The final answer is the count of distinct roots. It's O((m*n) * α(m*n)) and is preferred when the grid is dynamic (cells added one at a time).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →