Skip to main content

17. Number of Islands

mediumAsked at Instacart

Count connected land regions in a 2D grid — Instacart interviewers use this to test whether you can model a store's floor-map zones and traverse them efficiently for pick-path planning.

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

Problem

Given an m x n 2D binary grid 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. You may assume all four edges of the grid are surrounded by water.

Constraints

  • 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

Explanation: All connected land cells form one island.

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 DFS with visited set

Track visited cells in a separate set and DFS from each unvisited land cell.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  const visited = new Set();
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n) return;
    if (visited.has(`${r},${c}`) || grid[r][c] === '0') return;
    visited.add(`${r},${c}`);
    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' && !visited.has(`${r},${c}`)) {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff:

2. In-place DFS (sink visited land)

Mark each visited land cell as '0' in place to avoid extra space. BFS or DFS from each unvisited '1', incrementing the island count.

Time
O(m*n)
Space
O(min(m,n)) call stack
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;

  function 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:

Instacart-specific tips

Instacart grades graph traversal on store-layout problems — the in-place sink variant shows you understand when mutating input saves memory without sacrificing correctness. Be ready to extend to BFS and explain why BFS is preferred when recursion depth risks stack overflow on large grids.

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

Practice these live with InterviewChamp.AI →