Number of Islands

Problem Statement

Given a 2D grid of "1" (land) and "0" (water), count the number of islands. An island is a group of 4-directionally connected land cells. The grid is surrounded by water on all sides.

Example 1:

Input:
[
  ["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:
[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

Difficulty: Medium

---

Pattern Recognition

• What is the structure of the input? A 2D grid whose land cells form an implicit graph (4-connectivity).
• What are we counting? Connected components of 1s.
• What pattern does this suggest? Graph traversal — DFS or BFS — iterating every cell once.
• Why does this pattern fit? Counting connected components is the textbook use case for flood fill. Every land cell belongs to exactly one component; you walk each component to completion the first time you hit any of its cells.

---

Approach

Brute Force — Union-Find

Scan every land cell and union it with its land neighbors. At the end, count distinct roots.

Time: O(m * n * α(m*n)) with path compression and rank. Space: O(m * n). Why insufficient: Not actually worse asymptotically — it is a fine alternative. But DFS/BFS are simpler and equally fast here, so they are preferred unless the grid is streamed.

Optimal — DFS Flood Fill

Key Insight: The first time you hit a '1', start a DFS and convert the entire connected component to '0'. Each cell is visited once across the whole algorithm, and each visit kills one cell, so the outer loop only triggers a new DFS once per island.

Step-by-step:

1. Loop over every cell.
2. If you see '1', increment the island count and launch DFS from it.
3. DFS marks the cell '0' and recurses into its four neighbors.
4. Return the count.

Time: O(m * n) — each cell is read once and flipped at most once. Space: O(m * n) in the worst case (a single spiral island fills the recursion stack).

---

Walkthrough

Grid:

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

Outer loop visits cells row-major.

Cell	Value	Action	Count	Grid after DFS
(0,0)	1	DFS floods (0,0), (0,1), (1,0)	1	First island zeroed
(0,1)	0 (was flooded)	skip	1	—
(1,3)	1	DFS floods (1,3), (2,3), (2,2)	2	Second island zeroed
remaining	0	skip	2	—

Answer: 2.

---

Implementation

TypeScript

function numIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;

  const dfs = (r: number, c: number) => {
    if (r < 0 || c < 0 || r >= rows || c >= cols || 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 < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

C++

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size(), cols = grid[0].size(), count = 0;
        function<void(int,int)> dfs = [&](int r, int c) {
            if (r < 0 || c < 0 || r >= rows || c >= cols || 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 (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (grid[r][c] == '1') { ++count; dfs(r, c); }
        return count;
    }
};

Watch out: Mutating the input grid. If the interviewer says "don't mutate," use a separate visited set — same algorithm, just another boolean grid.

Watch out: Stack overflow on massive islands with recursive DFS. For a 300x300 all-land grid that is 90k frames — fine in C++, usually fine in JS, but mention the iterative stack / BFS alternative.

Watch out: Bounds checks. A common bug is inverting rows / cols in the index comparison.

---

Complexity Analysis

	Time	Space
Union-Find	O(m * n * α)	O(m * n)
DFS / BFS	O(m * n)	O(m * n)

Bottleneck: Every cell must be examined at least once. The DFS amortizes to O(1) per cell because each cell is only visited once total.

---

Edge Cases

1. Empty grid — Return 0.
2. All water — No DFS triggered, count stays 0.
3. All land — One DFS fills everything, return 1.
4. Single cell — Return 1 if it's land, 0 otherwise.
5. Long thin spiral — Recursion depth can approach m * n; use BFS if you're worried.
6. Diagonally adjacent land — They are NOT connected under 4-directional rules. Easy to misread.

---

Related Problems

• LC 695 — Max Area of Island: Same flood fill, track area per component.
• LC 463 — Island Perimeter: Single-pass counting of border edges.
• LC 1020 — Number of Enclaves: Flood-fill from borders first, then count remaining land.
• LC 305 — Number of Islands II: Streamed adds — now Union-Find is clearly better.

---

What Is Expected at Each Level?

Junior / New Grad: Recognize flood-fill. Implement recursive DFS. May mix up 4-directional vs 8-directional; should clarify.

Mid-level: Write clean DFS, handle bounds correctly, discuss whether mutating the grid is acceptable. Mention the BFS and Union-Find alternatives when asked.

Senior: Proactively cover all three approaches and when each is better: DFS for simplicity, BFS to avoid stack overflow, Union-Find for streamed or dynamically-connecting inputs. Discuss parallelism (disjoint grid chunks) and cache locality of row-major traversal.