Skip to main content

15. Number of Islands

mediumAsked at Riot Games

Count connected components of land on a 2D grid — Riot uses the same flood-fill structure for map-region partitioning and minimap pathfinding.

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

Problem

Given an m x n grid of '1's (land) and '0's (water), return the number of islands. An island is a maximal group of 4-directionally connected land cells.

Constraints

  • 1 <= m, n <= 300
  • Cells are '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','1','0']]
Output
1

Approaches

1. Brute mark with copy

Copy the grid then BFS/DFS each '1' marking visited cells in a side structure.

Time
O(m*n)
Space
O(m*n)
// Allocate a separate visited matrix
// For each unvisited '1', BFS and mark all reachable cells visited
// Increment counter

Tradeoff:

2. DFS flood-fill in place

Iterate the grid; on each '1', DFS and sink connected land to '0', incrementing a counter. Same in-place region sweep Riot uses to label connected lanes on the Summoner's Rift minimap each tick.

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

Tradeoff:

Riot Games-specific tips

Riot wants you to discuss DFS stack depth versus BFS queue width before you start coding — the same tradeoff they weigh when picking BFS for low-latency region-of-vision updates on the server tick.

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

Practice these live with InterviewChamp.AI →