Skip to main content

15. Number of Islands

mediumAsked at Chegg

Count connected components of '1's in a 2D grid — a graph traversal problem that mirrors Chegg's recommendation engine grouping related educational content.

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

Example 2

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

Approaches

1. Brute force

Use a visited set and run BFS/DFS from every unvisited land cell.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  const visited = new Set();
  let count = 0;
  for (let i = 0; i < grid.length; i++)
    for (let j = 0; j < grid[0].length; j++)
      if (grid[i][j] === '1' && !visited.has(`${i},${j}`)) {
        count++;
        bfs(grid, i, j, visited);
      }
  return count;
}

Tradeoff:

2. In-place DFS flood fill

Mark visited cells by mutating '1' to '0' during DFS — eliminates the visited set entirely and reduces space to the call stack depth.

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

Tradeoff:

Chegg-specific tips

Chegg often asks about graph traversal in the context of grouping related content clusters — mention how this maps to connected-component analysis in recommendation graphs.

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

Practice these live with InterviewChamp.AI →