Skip to main content

200. Number of Islands

mediumAsked at Canva

Count connected regions of '1's in a binary grid — Canva applies connected-component logic to detect isolated element groups on a canvas, making this a strong signal for how you think about spatial partitioning in a design editor.

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

Problem

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

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

Explanation: All '1' cells are connected, forming one island.

Example 2

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

Approaches

1. DFS flood fill

For each unvisited '1', increment the count and DFS-flood the entire connected region, marking cells as visited by overwriting them.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  let count = 0;
  const m = grid.length;
  const n = grid[0].length;
  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // mark visited
    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:

2. BFS flood fill

Same logic as DFS but uses an explicit queue — avoids call-stack overflow on large grids and is often preferred in production systems.

Time
O(m*n)
Space
O(min(m,n))
function numIslands(grid) {
  let count = 0;
  const m = grid.length;
  const n = grid[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        count++;
        grid[r][c] = '0';
        const queue = [[r, c]];
        while (queue.length > 0) {
          const [row, col] = queue.shift();
          for (const [dr, dc] of dirs) {
            const nr = row + dr;
            const nc = col + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === '1') {
              grid[nr][nc] = '0';
              queue.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return count;
}

Tradeoff:

Canva-specific tips

Canva's design engine partitions elements into render groups — think of selecting all elements in a bounded region. Interviewers care whether you reason about the DFS stack depth: on a 300×300 all-'1' grid, recursive DFS can hit 90,000 stack frames and crash. Mention BFS or iterative DFS as the production-safe choice and explain why. Also address the mutation trade-off: overwriting the grid is fast but destroys the input — ask whether the caller needs the original intact before you do it.

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

Practice these live with InterviewChamp.AI →