Skip to main content

200. Number of Islands

mediumAsked at LinkedIn

Count connected landmasses in a grid using BFS or DFS — LinkedIn uses this to probe how you think about connected-component discovery, the same graph reasoning behind mapping professional networks and finding isolated clusters in the member graph.

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

Problem

Given an m x n 2D binary grid where '1' represents land and '0' represents 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","0"],["1","1","0","0","0"],["0","0","0","1","0"]]
Output
2

Explanation: Two connected landmasses exist: one in the top-left, one at row 2 col 3.

Example 2

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

Approaches

1. Brute force DFS with visited set

Track visited cells in a separate Set. Iterate the grid; on each unvisited '1', DFS the connected component, marking all reachable cells visited.

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

Tradeoff:

2. Sink (in-place mark) BFS — optimal

Instead of a separate visited structure, mark visited '1' cells as '0' (sink them) during BFS. Saves O(m*n) extra space and is the canonical LinkedIn answer.

Time
O(m*n)
Space
O(min(m,n)) BFS queue
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let islands = 0;
  function bfs(r, c) {
    const queue = [[r, c]];
    grid[r][c] = '0';
    while (queue.length) {
      const [row, col] = queue.shift();
      for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
        const nr = row+dr, nc = col+dc;
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === '1') {
          grid[nr][nc] = '0';
          queue.push([nr, nc]);
        }
      }
    }
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') { bfs(r, c); islands++; }
    }
  }
  return islands;
}

Tradeoff:

LinkedIn-specific tips

LinkedIn grades this on two axes: (1) Do you narrate the connected-component framing — not just 'it's a grid BFS'? Tie it to why LinkedIn cares: finding cohesive clusters in the member graph. (2) Do you discuss the sink-in-place optimization unprompted? The follow-up is almost always 'can you avoid the extra visited structure?' — be ready to say 'yes, mark visited cells as 0.' DFS also passes but BFS is preferred because it avoids recursion-stack blowup on a 300×300 grid.

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

Practice these live with InterviewChamp.AI →