Skip to main content

16. Number of Islands

mediumAsked at Autodesk

Count connected groups of land cells in a 2D grid of '1's and '0's.

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

Problem

Given an m x n 2D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and 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. Union-find on cells

Treat every land cell as a node and union with adjacent land neighbors, then count roots.

Time
O(mn * alpha)
Space
O(mn)
for each land cell, union with right/down land neighbor;
then count unique roots over land cells.

Tradeoff:

2. DFS flood fill

Scan the grid; on each unvisited land cell increment the counter and DFS to mark every connected land cell as water.

Time
O(mn)
Space
O(mn)
function numIslands(grid) {
  let count = 0;
  const m = grid.length, n = grid[0].length;
  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);
  }
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) {
    if (grid[i][j] === '1') { count++; dfs(i, j); }
  }
  return count;
}

Tradeoff:

Autodesk-specific tips

Connected-component sweeps over grids parallel how Autodesk segments raster regions when vectorizing scanned drawings.

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

Practice these live with InterviewChamp.AI →