Skip to main content

16. Number of Islands

mediumAsked at Intuit

Count the number of connected '1' regions in a 2D grid of '1' (land) and '0' (water). Intuit asks this as the canonical DFS/BFS-on-grid problem and reframes it as 'count distinct expense clusters' for financial-graph candidates.

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— Intuit onsite — graph traversal under the 'expense clustering' framing.
  • Blind (2025-12)— Intuit SWE II loop included Number of Islands as the medium coding round.

Problem

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

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

Explanation: Top-left L-shape is one island; the bottom-right single cell is another.

Example 2

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

Approaches

1. Brute force with visited set

For each unvisited land cell, BFS/DFS to flood-fill its component, marking visited externally in a Set.

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

Tradeoff: Correct but the string-key Set adds overhead. In-place mutation is faster.

2. DFS with in-place sink (optimal)

For each unvisited '1', DFS the connected component and sink each visited cell to '0'. No external visited structure needed; recursion stack is the only extra space.

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;
  function sink(r, c) {
    if (r<0||c<0||r>=m||c>=n||grid[r][c]!=='1') return;
    grid[r][c] = '0';
    sink(r+1,c); sink(r-1,c); sink(r,c+1); sink(r,c-1);
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') { sink(r, c); count++; }
    }
  }
  return count;
}

Tradeoff: Linear in cells. In-place mutation eliminates the visited Set; recursion depth bounded by grid size.

Intuit-specific tips

Intuit reframes this as 'count distinct transaction clusters where adjacency = same merchant + same day' — the algorithm is identical, the adjacency function changes. They grade for whether you ask about diagonal connectivity (the default is 4-directional). Bonus signal: discuss BFS for grids where recursion depth would blow the stack (worst case 90,000 cells on a 300x300 grid).

Common mistakes

  • Mutating the grid when the caller doesn't expect it — ask first.
  • Using JSON.stringify or string keys for visited — slow and allocs heavy.
  • Forgetting to guard bounds (off-by-one on grid.length / grid[0].length).

Follow-up questions

An interviewer at Intuit may pivot to one of these next:

  • Max Area of Island — return the area of the largest island (LC 695).
  • Number of Islands II — dynamic add-land queries (LC 305, needs Union-Find).
  • Number of Distinct Islands — count unique shapes (LC 694).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why sink to '0' instead of using a visited set?

Sinking mutates the grid but eliminates auxiliary memory and avoids string-key allocations. If the caller needs the grid preserved, restore it after or clone first.

When should I use BFS instead of DFS here?

Use BFS when the grid is very large and recursion depth might blow the call stack (e.g., a 300x300 all-land grid would recurse 90,000 deep). BFS uses an explicit queue and bounded heap memory.

Practice these live with InterviewChamp.AI

Drill Number of Islands and other Intuit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →