Skip to main content

13. Number of Islands

mediumAsked at Flipkart

Count connected groups of land cells in a grid — Flipkart maps it to clustering nearby pincodes for warehouse coverage analysis.

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

Problem

Given an m x n 2D grid of '1's (land) and '0's (water), return the number of islands. An island is a group of '1's connected 4-directionally surrounded by water.

Constraints

  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'

Examples

Example 1

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

Example 2

Input
grid = [['1','0','1'],['0','0','0'],['1','0','1']]
Output
4

Approaches

1. Union-Find

Treat every land cell as a node, union with right/down neighbors, count roots.

Time
O(m*n * α)
Space
O(m*n)
// build DSU over land cells, union neighbors, count unique parents

Tradeoff:

2. DFS flood fill

Iterate cells; on each '1' run DFS, marking visited cells '0' in place. Count one increment per DFS entry. Linear scan, no extra grid.

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

Tradeoff:

Flipkart-specific tips

Flipkart interviewers like a quick mention of iterative BFS for large grids — their pincode coverage maps blow the call stack with recursion.

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

Practice these live with InterviewChamp.AI →