Skip to main content

19. Number of Islands

easyAsked at Tripadvisor

Count disconnected landmasses in a grid — Tripadvisor uses this graph-traversal pattern to reason about clustering isolated attraction zones or destination regions on their travel maps.

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. You may assume all four edges of the grid are 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. Brute force DFS with visited set

Iterate every cell; when a '1' is found, DFS all connected land cells marking them in a separate visited set.

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(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] === '0') return;
    visited[r][c] = true;
    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[r][c]) { dfs(r, c); count++; }
    }
  }
  return count;
}

Tradeoff:

2. In-place DFS (sink visited land)

Mutate the grid: when a '1' is found, DFS and overwrite connected '1's with '0' to avoid a separate visited structure. O(1) extra space.

Time
O(m*n)
Space
O(m*n) call stack
function numIslands(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  function sink(r, c) {
    if (r < 0 || r >= m || c < 0 || 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:

Tripadvisor-specific tips

Tripadvisor interviewers want to see you connect the grid abstraction to real product logic — think clustering isolated attraction regions or identifying disconnected destination groups. Mention that in production the grid might be enormous (full world map), so discuss BFS with an explicit queue to avoid call-stack overflow. They also appreciate noting the in-place vs. immutable input tradeoff before diving into code.

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

Practice these live with InterviewChamp.AI →