Number of Islands — The #1 Grid Traversal Question at FAANG

Problem Statement#

Given an m x n 2D binary 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 surrounded by water.

Constraints:

• 1 <= m, n <= 300
• grid[i][j] is '0' or '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

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

Input:  grid = [["0"]]
Output: 0

Why This Problem Matters#

LeetCode 200 Number of Islands is consistently ranked the most frequently asked grid problem on the internet. It has appeared at Google, Amazon, Meta, Microsoft, Bloomberg, Goldman Sachs, Citadel, Cloudflare, DoorDash, and dozens more — often as the warmup problem before a harder graph question.

Why is it so popular?

• It tests whether you can recognize a connected components problem disguised as a grid puzzle.
• It naturally extends to Union-Find, BFS, and DFS so the interviewer can probe whichever pattern they want.
• It is short enough to code in 10 minutes but rich enough to discuss optimizations for 30.
• Real applications: image segmentation, region labeling in computer vision, pathogen cluster detection, and game-of-life style cellular automata.

If you can articulate Number of Islands cleanly, the interviewer trusts you with the harder follow-ups: Number of Islands II (online updates), Surrounded Regions, Pacific Atlantic Water Flow, and Max Area of Island.

The Core Insight#

The grid is a graph in disguise. Each land cell is a node, and each pair of horizontally or vertically adjacent land cells is an edge. The number of islands is the number of connected components in this implicit graph.

The optimal algorithm is:

1. Iterate over every cell.
2. When you hit an unvisited land cell, increment the island counter.
3. Run BFS or DFS from that cell, marking every reachable land cell as visited so you do not count it again.

Both BFS (queue, FIFO) and DFS (stack or recursion, LIFO) achieve O(m*n) time and O(m*n) space. BFS is preferred for huge grids because Python recursion can hit stack limits around depth 1000.

A third approach — Union-Find — is also valid and shines when the grid is updated incrementally (LC 305 Number of Islands II).

Visual Dry Run#

Grid:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Final answer: 3.

The queue at step 1 evolves like this:

Solution (Optimal)#

# Python — BFS with a queue, O(m*n) time, O(min(m,n)) space for queue
from collections import deque
 
def numIslands(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0
 
    m, n = len(grid), len(grid[0])
    islands = 0
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
 
    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                islands += 1
                queue = deque([(r, c)])
                grid[r][c] = '0'  # mark as visited
 
                while queue:
                    x, y = queue.popleft()
                    for dx, dy in dirs:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                            grid[nx][ny] = '0'
                            queue.append((nx, ny))
 
    return islands

// JavaScript — DFS with recursion, O(m*n) time, O(m*n) worst-case stack
function numIslands(grid) {
    if (!grid.length || !grid[0].length) return 0;
    const m = grid.length, n = grid[0].length;
    let islands = 0;
 
    const dfs = (r, c) => {
        if (r < 0 || r >= m || c < 0 || c >= n || 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 < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === '1') {
                islands++;
                dfs(r, c);
            }
        }
    }
 
    return islands;
}

Complexity:

Common Mistakes#

1. Marking visited too late. If you mark (nr, nc) as visited only when popping it, the same cell can be enqueued multiple times, blowing up memory. Mark it on enqueue, not on dequeue.

2. Comparing against integer instead of string. The input cells are characters '0' and '1', not integers. grid[r][c] == 1 will always be False in Python.

3. Stack overflow on DFS. A 300x300 grid that is all '1' can recurse 90,000 deep. Switch to iterative BFS or use sys.setrecursionlimit(10**6) on platforms that allow it.

4. Using a separate visited set when not needed. Mutating the grid is O(1) extra space; a separate set is O(m*n). If the interviewer forbids mutation, then the set is required.

5. Counting diagonally connected cells as one island. The problem says only 4-directional adjacency. Diagonals stay separate.

Interview Tips#

• State the pattern explicitly: "This is a connected components problem on an implicit grid graph. I will iterate over cells; each unvisited land cell triggers a BFS that floods its component."
• Mention both BFS and DFS. Then pick BFS if the grid is large, DFS if recursion is acceptable. Recruiters love this nuance.
• Ask whether the input grid can be mutated. If yes, save the visited set space.
• Bring up Union-Find as the right tool for the streaming variant (LC 305). Even if you do not implement it, naming it shows breadth.

Follow-up Questions#

1. Number of Islands II (LC 305). Lands are added one at a time; return the count after each addition. Use Union-Find with path compression.
2. Max Area of Island (LC 695). Return the largest island area, not the count. Same DFS/BFS but accumulate area.
3. Surrounded Regions (LC 130). Reverse the problem — flip all 'O' regions not connected to the border.
4. Pacific Atlantic Water Flow (LC 417). Multi-source BFS from each ocean.
5. Number of Distinct Islands (LC 694). Hash the shape signature of each island; count distinct hashes.

Key Takeaways#

• Number of Islands is the canonical connected components problem on a grid; recognize the pattern instantly in interviews.
• BFS uses a queue (FIFO) and DFS uses a stack (LIFO or recursion); both run in O(m*n) time.
• Mark cells visited on enqueue, not on dequeue, to prevent duplicate processing.
• Mutating the grid is the simplest way to track visited cells when the interviewer allows it; otherwise use a set.
• The same template solves Max Area of Island, Surrounded Regions, Walls and Gates, and Pacific Atlantic Water Flow.
• Union-Find is the right structure when islands are added or queried incrementally — name-drop it in the follow-up discussion.