Skip to main content

200. Number of Islands

mediumAsked at Amazon

Given a 2D grid of '1's and '0's, count the number of islands. Amazon asks this to test whether you reach for DFS/BFS flood-fill and articulate why each cell is visited at most once for O(m*n).

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

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as a recurring graph staple.
  • Blind (2025-11)— Recurring Amazon interview problem.

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 flood-fill (optimal)

For each unvisited land cell, DFS and mark every connected land cell as visited. Each DFS launch is a new island.

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(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // mark visited by sinking the land
    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') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff: Each cell visited at most twice (once by the outer loop, once during DFS). Mutating the grid avoids a separate visited set. Recursion depth = island size — fine within constraint.

2. BFS flood-fill (alternative)

Same idea but iterative — use a queue instead of recursion.

Time
O(m * n)
Space
O(min(m, n))
function numIslandsBFS(grid) {
  const m = grid.length, n = grid[0].length;
  let count = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] !== '1') continue;
      count++;
      const q = [[r, c]];
      grid[r][c] = '0';
      while (q.length) {
        const [cr, cc] = q.shift();
        for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
          const nr = cr + dr, nc = cc + dc;
          if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            q.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

Tradeoff: Same complexity. BFS uses an explicit queue instead of the call stack — safer for very large islands that might blow the stack.

Amazon-specific tips

Amazon interviewers grade this on the flood-fill recognition. State out loud: 'Every land cell belongs to exactly one island. I'll iterate the grid; the first land cell I hit launches a new island count and a flood-fill that marks all its neighbors as visited.' DFS vs BFS doesn't matter much; pick what you can code cleanly.

Common mistakes

  • Forgetting to mark cells as visited — leads to counting the same island multiple times.
  • Counting diagonals as adjacent — the problem only counts horizontal/vertical.
  • Allocating a separate visited 2D array when mutating the grid is permissible (saves O(mn) memory).

Follow-up questions

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

  • Number of Islands II (LC 305): islands as adds come in (union-find).
  • Max Area of Island (LC 695): return the size of the largest island.
  • Surrounded Regions (LC 130): a variant where boundary-connected regions don't count.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

DFS or BFS — which does Amazon prefer?

Both score equally. DFS is shorter to write; BFS is safer on huge inputs (no stack overflow). The flood-fill insight is what matters.

Is mutating the grid acceptable?

Yes unless the interviewer explicitly says no. Mutating saves O(m*n) extra memory. If they say no, use a Set of visited (r, c) keys.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →