Skip to main content

70. Number of Islands

mediumAsked at Salesforce

Count the number of connected components of 1s in a 2D grid. Salesforce uses this as the canonical grid-DFS/BFS problem.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses connected-components in their territory-clustering for accounts.
  • Blind (2025-11)— Recurring on Salesforce backend onsites.

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

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. DFS with visited array

Separate visited matrix; DFS from each unvisited 1.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  const visited = Array.from({ length: m }, () => new Array(n).fill(false));
  let count = 0;
  function dfs(i, j) {
    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || grid[i][j] === '0') return;
    visited[i][j] = true;
    dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1);
  }
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) {
    if (grid[i][j] === '1' && !visited[i][j]) { dfs(i, j); count++; }
  }
  return count;
}

Tradeoff: Extra O(m*n) for visited array. Can be saved by mutating grid.

2. DFS with in-place mutation (sink island)

Sink each visited cell by setting to '0'. Avoids separate visited tracking.

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 dfs(i, j) {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === '0') return;
    grid[i][j] = '0';
    dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1);
  }
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) {
    if (grid[i][j] === '1') { dfs(i, j); count++; }
  }
  return count;
}

Tradeoff: Mutates grid but avoids separate visited array. Recursion stack worst case O(m*n) for a single huge island.

Salesforce-specific tips

Salesforce uses connected-components for territory clustering (sales territories must be geographically connected). They grade on whether you reach for DFS/BFS instantly. Bonus signal: discuss using Union-Find for streaming additions of 1s — LC 305 (Number of Islands II).

Common mistakes

  • Not skipping water cells — wasted recursion on '0' cells.
  • Counting the same island multiple times — only count on the FIRST DFS triggering call.
  • Recursion stack overflow on huge inputs — switch to iterative BFS.

Follow-up questions

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

  • Number of Islands II (LC 305) — online, with adds.
  • Max Area of Island (LC 695).
  • Surrounded Regions (LC 130).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

BFS or DFS?

Both work; DFS is slightly shorter recursively but risks stack overflow. BFS uses a queue and bounded memory. For Salesforce production, BFS is preferred.

Could I use Union-Find?

Yes — it's O(m*n * α(m*n)) which is essentially O(m*n). Useful when islands are dynamically added (LC 305).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →