Skip to main content

14. Number of Islands

mediumAsked at LINE

Count the number of distinct islands in a 2D grid of land and water — LINE uses this to gauge whether you reach for clean DFS/BFS flood-fill before more exotic structures.

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 surrounded by water and formed by connecting adjacent lands horizontally or vertically. You may assume all four edges are surrounded by water.

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

Approaches

1. Union-Find

Treat each land cell as a node, union adjacent land cells, count distinct roots.

Time
O(m*n*α)
Space
O(m*n)
// DSU with path compression + union by rank.
// More moving parts than the DFS approach.

Tradeoff:

2. DFS flood fill

Scan the grid; on every unvisited land cell, increment the counter and DFS to sink the whole connected component by overwriting visited land with '0'.

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

Tradeoff:

LINE-specific tips

At LINE, mention you'd use the same connected-component scan to find clusters of chat rooms that share a sticker-pack subscription — sticker-delivery framing wins.

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

Practice these live with InterviewChamp.AI →