Skip to main content

17. Number of Islands

mediumAsked at Figma

Count connected components of land in a 2D grid. Figma uses this to probe how you'd flood-fill a selection or count grouped layers on the canvas.

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

Problem

Given an m x n 2D grid of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and 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","1","0"],["0","0","1"]]
Output
2

Example 2

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

Approaches

1. Naive scan-and-mark with extra grid

Allocate a visited matrix and BFS from every unvisited land cell.

Time
O(m * n)
Space
O(m * n)
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  const seen = Array.from({ length: m }, () => new Array(n).fill(false));
  // BFS from each unseen '1'; omitted body
  return 0;
}

Tradeoff:

2. In-place DFS flood fill

Mutate the grid as you traverse — set visited cells to '0'. Saves the visited matrix, mirrors how a selection flood-fill mutates the canvas hit-test buffer directly.

Time
O(m * n)
Space
O(m * n)
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  const 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:

Figma-specific tips

Figma loves it when you tie the flood-fill back to canvas hit-testing — explain that the same algorithm powers magic-wand selection at scale.

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

Practice these live with InterviewChamp.AI →