Skip to main content

9. Number of Islands

mediumAsked at Rappi

Count connected '1' clusters in a grid — Rappi frames this as counting connected delivery-demand hotspots on a city heatmap to allocate courier supply.

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

Problem

Given an m x n grid of '1' (land) and '0' (water), return the number of islands. An island is formed by connecting adjacent lands horizontally or vertically.

Constraints

  • 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

Example 2

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

Approaches

1. Brute union-find per pair

For every land cell pair, check connectivity by repeated BFS.

Time
O((mn)^2)
Space
O(mn)
// for each land cell, BFS from it and compare visited sets pairwise — quadratic in cells, only acceptable as a baseline.

Tradeoff:

2. DFS flood-fill

Scan the grid; on each unvisited '1' flood-fill its component and bump the island count.

Time
O(mn)
Space
O(mn)
function numIslands(g) {
  let n = 0;
  const fill = (i, j) => {
    if (i<0||j<0||i>=g.length||j>=g[0].length||g[i][j]!=='1') return;
    g[i][j] = '0';
    fill(i+1,j); fill(i-1,j); fill(i,j+1); fill(i,j-1);
  };
  for (let i=0;i<g.length;i++) for (let j=0;j<g[0].length;j++)
    if (g[i][j]==='1') { n++; fill(i,j); }
  return n;
}

Tradeoff:

Rappi-specific tips

Rappi grades for the in-place flood-fill — they want you to mutate the grid rather than allocate a visited set, mirroring how their hotspot-clustering job runs over a shared mmap'd tile.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →