Skip to main content

19. Number of Islands

mediumAsked at Coursera

Count connected components of land cells in a grid, a BFS/DFS graph problem Coursera uses to evaluate traversal skills relevant to course dependency graph analysis.

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
  • grid[i][j] is '0' or '1'

Examples

Example 1

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

Example 2

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

Approaches

1. Brute force (visited matrix + DFS per cell)

Use a separate boolean matrix to track visits — same asymptotic cost but extra O(m*n) space.

Time
O(m*n)
Space
O(m*n)
// Uses separate visited matrix — extra space
function numIslands(grid) {
  const visited = grid.map(r => r.map(() => false));
  let count = 0;
  function dfs(r, c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
    if (visited[r][c] || grid[r][c] === '0') return;
    visited[r][c] = true;
    [[1,0],[-1,0],[0,1],[0,-1]].forEach(([dr,dc]) => dfs(r+dr, c+dc));
  }
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[0].length; c++)
      if (grid[r][c] === '1' && !visited[r][c]) { dfs(r,c); count++; }
  return count;
}

Tradeoff:

2. In-place DFS (sink visited land)

Mark visited '1' cells as '0' in-place to avoid a visited matrix. Each cell is processed once making it O(m*n) time and O(m*n) stack space in worst case.

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

Tradeoff:

Coursera-specific tips

Coursera interviews emphasize algorithms for educational platforms, content recommendation systems, and scalable delivery pipelines. Medium-difficulty graph and DP problems are typical.

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

Practice these live with InterviewChamp.AI →