Skip to main content

87. Number of Islands

mediumAsked at Ola

Count the number of connected '1' islands in a 2D grid.

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

Problem

Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300

Examples

Example 1

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

Example 2

Input
grid = [["0"]]
Output
0

Approaches

1. Union-Find

Union each '1' cell with neighbors; count remaining components.

Time
O(m*n*alpha)
Space
O(m*n)
// DSU/Union-Find approach

Tradeoff:

2. DFS flood fill

Iterate cells; for each '1', DFS-mark all connected '1's to '0' and increment a counter.

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

Ola-specific tips

Ola favors the in-place flood-fill; tie it to counting connected demand clusters on a real-time city-grid heatmap.

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

Practice these live with InterviewChamp.AI →