Skip to main content

14. Number of Islands

mediumAsked at Baidu

Count connected components of land cells in a 2D grid where '1' is land and '0' is water.

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 land cells connected horizontally or vertically; assume the grid is bounded by water.

Constraints

  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'

Examples

Example 1

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

Example 2

Input
grid = [['0','0'],['0','0']]
Output
0

Approaches

1. Union find

Union each land cell with its right and down land neighbors; the final count of unique roots is the island count.

Time
O(mn * alpha(mn))
Space
O(mn)
// build parent[] of size m*n, union land-land neighbors; count distinct roots in land cells.
// Correct but more code than DFS for an on-screen whiteboard.

Tradeoff:

2. DFS flood fill

Scan the grid; on each unvisited '1' increment the counter and DFS to mark its entire component as visited.

Time
O(mn)
Space
O(mn)
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:

Baidu-specific tips

Baidu uses flood-fill style traversals on heat-map grids for ad-ranking geographic CTR clusters, so they want the iterative-stack variant ready in case interviewer flags recursion depth on 300x300 grids.

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

Practice these live with InterviewChamp.AI →