Skip to main content

23. Number of Islands

mediumAsked at Coupang

Count connected land regions in a grid, mirroring how Coupang's same-day delivery routing partitions warehouses into connected coverage zones from a 2D capacity map.

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

Problem

Given an m x n 2D binary grid where '1' is land and '0' is water, return the number of islands. Islands are surrounded by water and formed by connecting adjacent land cells horizontally or vertically.

Constraints

  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'

Examples

Example 1

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

Example 2

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

Approaches

1. Brute counting via marker

Scan each cell, BFS or DFS flood-fill on encountering land, but mutate the grid.

Time
O(m*n)
Space
O(m*n) worst case for recursion stack
function dfs(i, j) {
  if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] !== '1') return;
  grid[i][j] = '0';
  dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1);
}

Tradeoff:

2. Iterative BFS with queue

Sweep cells; when you find an unvisited '1', BFS-flood it and increment a counter. Avoids recursion-stack overflow on dense grids.

Time
O(m*n)
Space
O(min(m,n))
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] !== '1') continue;
      count++;
      const q = [[i, j]];
      while (q.length) {
        const [r, c] = q.shift();
        if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] !== '1') continue;
        grid[r][c] = '0';
        q.push([r+1, c], [r-1, c], [r, c+1], [r, c-1]);
      }
    }
  }
  return count;
}

Tradeoff:

Coupang-specific tips

Coupang's same-day delivery routing partitions warehouses into connected coverage zones from a 2D capacity map; iterative BFS avoids stack-overflow risk on large district grids during peak-event throughput.

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 Coupang interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →