Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Number of Islands (LC 200)

Problem Statement

Given an m x n 2D grid of '1' (land) and '0' (water), count the number of islands. An island is a connected cluster of land connected horizontally or vertically (not diagonally). The grid is bounded by water.

Example 1:

Input:
11110
11010
11000
00000
Output: 1

Example 2:

Input:
11000
11000
00100
00011
Output: 3

Constraints:

• 1 <= m, n <= 300
• Cell is '0' or '1'.

Difficulty: Medium

---

Pattern Recognition

• Input structure: 2D grid, cells are binary.
• What are we counting? connected components.
• Pattern: grid DFS/BFS (76% of Google L4 loops include graphs). Union-Find is an elegant alternative.
• Why: each land cell belongs to exactly one component. Launch a flood fill from any unvisited land cell, mark the whole component, increment the count.

---

Approach

Brute Force

Repeatedly scan the grid for unmarked land, flood fill from each, count. This is actually also the optimal approach — with grid problems, the "brute force" is DFS/BFS because the search space is the connected component itself.

Optimal — DFS Flood Fill

Key Insight: Every land cell is seen at most twice: once when discovered, once when visited by DFS. Total work is O(m * n).

count = 0
for each (i, j):
    if grid[i][j] == '1':
        count++
        dfs(i, j)   // marks whole component as visited

function dfs(i, j):
    if out of bounds or grid[i][j] != '1': return
    grid[i][j] = '0'               // mark visited in place
    dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)

You can use a separate visited set if mutating the grid is not allowed.

Time: O(m * n). Space: O(m * n) worst case for recursion stack.

Alternative — BFS (iterative)

Same asymptotic cost, but uses an explicit queue — safer against stack overflow on 300x300 grids.

Alternative — Union-Find

For each land cell, union with its up/left neighbors if they are land. Count the number of distinct roots. O(m * n * α(m * n)) time. Useful when islands are added dynamically (LC 305 Number of Islands II).

---

Walkthrough

Grid (3x4):

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

Scan top-left to bottom-right.

1. (0,0) = '1', count = 1, DFS:
   • marks (0,0), (0,1), (1,1) → stops (neighbors are '0' or out of bounds).
2. (0,2), (0,3), (1,0) all '0'.
3. (1,3) = '1', count = 2, DFS:
   • marks (1,3), (2,3) → stops.
4. (2,0) = '1', count = 3, DFS:
   • marks (2,0) → stops (neighbors '0').

Answer: 3.

---

Implementation

TypeScript

function numIslands(grid: string[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    let count = 0;

    const dfs = (i: number, j: number): void => {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== '1') return;
        grid[i][j] = '0'; // mark visited in place
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    };

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(i, j);
            }
        }
    }
    return count;
}

C++

class Solution {
    int m, n;
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return;
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
};

Watch out:

1. Mutating the input grid is often fine but flag it to the interviewer; ask whether a visited matrix is preferred.
2. Forgetting the bounds check before the cell-type check causes index errors on the border.
3. Recursive DFS may hit stack overflow on pathological inputs like a 300x300 all-land grid. Use BFS or iterative DFS with an explicit stack for safety.

---

Complexity Analysis

	Time	Space
DFS (recursive)	O(m * n)	O(m * n) stack worst case
BFS	O(m * n)	O(min(m, n)) typical
Union-Find	O(m * n * α(m * n))	O(m * n)

Bottleneck: you must at minimum touch every land cell. Union-Find becomes attractive only for the dynamic-update variant.

---

Edge Cases

1. Empty grid — constraints guarantee m, n >= 1, but defensive guard grid.length === 0 is cheap.
2. All water — return 0; no DFS ever fires.
3. All land — return 1; a single DFS visits everything.
4. Single row / single column — standard; DFS only branches on two directions effectively.
5. Large grid with deep connected component — recursive DFS may stack-overflow. Switch to BFS.
6. Mutation restriction — use a separate visited[m][n] array.

---

Related Problems

• LC 695 — Max Area of Island — Same traversal, track area per DFS call.
• LC 305 — Number of Islands II — Dynamic adds; Union-Find shines.
• LC 463 — Island Perimeter — Same traversal, accumulate border edges.
• LC 1020 — Number of Enclaves — DFS from borders first to eliminate edge-connected land.

---

What Is Expected at Each Level

Junior: Identify DFS on a grid, implement the recursive flood fill, state O(m*n) time.

Mid-level: Write it without bugs, propose BFS as a stack-safety backup, and confidently discuss whether to mutate vs use a visited set.

Senior (L4 target): Volunteer Union-Find as the answer if the interviewer asks "what if cells become land dynamically?" (LC 305), discuss constant-factor tradeoffs between DFS and BFS, and comment on parallelization — component labeling is embarrassingly parallel by stripe decomposition, which Google distributed-systems interviewers may probe.