Skip to main content

14. Number of Islands

mediumAsked at Byju's

Count connected land regions in a 2D grid of '1' (land) and '0' (water).

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. You may assume all four edges of the grid are surrounded by water.

Constraints

  • 1 <= m, n <= 300
  • grid[i][j] in {'0','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. Brute force visited set

Iterate each cell, check membership in a visited set, spawn DFS recursively for unvisited land.

Time
O(mn)
Space
O(mn)
const seen=new Set();let count=0;
function dfs(r,c){const k=r+','+c;if(r<0||c<0||r>=grid.length||c>=grid[0].length||grid[r][c]==='0'||seen.has(k))return;seen.add(k);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'&&!seen.has(r+','+c)){count++;dfs(r,c);}
return count;

Tradeoff:

2. DFS flood fill in place

Scan cells; for every fresh '1', flood-fill the connected land to '0' and bump a counter. Avoids the separate visited set entirely.

Time
O(mn)
Space
O(mn)
function numIslands(grid) {
  let count = 0;
  const m = grid.length, n = grid[0].length;
  const fill = (r, c) => {
    if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] !== '1') return;
    grid[r][c] = '0';
    fill(r+1,c); fill(r-1,c); fill(r,c+1); fill(r,c-1);
  };
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (grid[r][c] === '1') { count++; fill(r, c); }
  return count;
}

Tradeoff:

Byju's-specific tips

Byju's adaptive-learning grid-traversal asks often mirror their lesson-cluster topology, so frame islands as 'concept clusters' to win recruiter signal.

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

Practice these live with InterviewChamp.AI →