Skip to main content

19. Number of Islands

mediumAsked at Swiggy

Count the connected land regions in a 2-D grid of '1's and '0's.

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

Problem

Given an m x n grid of '1' (land) and '0' (water), return the number of islands. An island is a maximal four-directionally connected group of land cells.

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

Approaches

1. Union-find on cells

Union each land cell with its neighbors, then count distinct roots.

Time
O(m*n * alpha(m*n))
Space
O(m*n)
const N=m*n; const p=Array.from({length:N},(_,i)=>i);
function find(x){return p[x]===x?x:p[x]=find(p[x]);}
function union(a,b){p[find(a)]=find(b);}
// iterate land cells, union with 4 neighbors, then count unique roots over land

Tradeoff:

2. DFS flood fill

Scan the grid; on each unvisited land cell increment a counter and DFS to mark the entire island as visited (or sink it to '0').

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

Swiggy-specific tips

Swiggy uses connected-component questions to mirror how their delivery zones partition the city map; clean DFS with iterative stack is a Plus for production-readiness 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 Swiggy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →