Skip to main content

14. Number of Islands

mediumAsked at Brex

Count connected land regions in a 2D grid using BFS or DFS — a graph traversal staple that Brex uses to assess structured problem decomposition skills.

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

Problem

Given an m x n 2D binary grid filled with '1' (land) and '0' (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

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

Example 2

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

Approaches

1. Brute force with visited set

For each unvisited '1', launch a DFS and use a separate visited matrix.

Time
O(m*n)
Space
O(m*n)
// standard DFS with visited array — O(m*n) space
const visited = Array.from({length: m}, () => new Array(n).fill(false));
let count = 0;
for each cell: if '1' and not visited, dfs, count++;
return count;

Tradeoff:

2. In-place DFS (mutate grid)

Sink each island by flipping '1' cells to '0' as we DFS, avoiding a separate visited structure. This reduces space to O(min(m,n)) for the recursive call stack.

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

Tradeoff:

Brex-specific tips

Brex asks about fintech infrastructure, multi-currency handling, and spend management algorithms. Expect LeetCode-style DSA focused on hash maps, sorting, and dynamic programming.

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

Practice these live with InterviewChamp.AI →