Skip to main content

17. Number of Islands

mediumAsked at Freshworks

Count connected components in a grid — Freshworks frames it as counting independent tenant clusters in a sharded ticket grid.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a 2D 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.

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

Approaches

1. Brute force (recursive without marking)

DFS every land cell, but use a separate visited Set keyed by 'r,c'. Functional but doubles memory.

Time
O(m*n)
Space
O(m*n)
const visited = new Set();
function dfs(r,c){ /* uses visited.has + visited.add */ }

Tradeoff:

2. DFS with in-place sink

Scan the grid. On a '1', increment count and DFS-flood-fill that island to '0' so it isn't recounted.

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

Tradeoff:

Freshworks-specific tips

Freshworks will ask whether you're allowed to mutate the input — confirm, then prefer the in-place sink for the constant-extra-space win unless they say otherwise.

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

Practice these live with InterviewChamp.AI →