LeetCode · #200
Number of Islands Solution
Given an m × n grid of '1' (land) and '0' (water), count the number of islands — connected groups of land cells using 4-directional adjacency.
01
Section One · Problem
Problem Statement
Given an m × n 2D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.
Example
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1 // all '1' cells are connected — one island
Constraints
• m == grid.length, n == grid[i].length • 1 ≤ m, n ≤ 300 ← up to 90,000 cells; O(m·n) solution required • grid[i][j] is '0' or '1'
02
Section Two · Approach 1
Brute Force — Separate Visited Array
Scan every cell. When a land cell that hasn't been visited is found, increment the island count and mark all cells reachable from it as visited using a DFS with a separate boolean[][] visited grid. This correctly counts connected components.
Why it works
Each DFS call fully explores one connected component (island), marking all cells visited. The outer loop ensures every starting cell is considered. The count of DFS calls from unvisited land cells equals the number of islands.
Why we can do better
Problem: The separate
visited[][] array uses O(m·n) extra space. We can instead mark cells in-place by overwriting '1' with '0' during the flood-fill — no extra grid needed. The input is not explicitly required to be immutable in this problem, so in-place mutation is the standard competitive approach.
Java — DFS with visited array
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length, count = 0;
boolean[][] vis = new boolean[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (!vis[r][c] && grid[r][c] == '1') {
dfs(grid, vis, r, c);
count++;
}
return count;
}
private void dfs(char[][] g, boolean[][] v, int r, int c) {
if (r < 0 || r >= g.length || c < 0 || c >= g[0].length
|| v[r][c] || g[r][c] == '0') return;
v[r][c] = true;
dfs(g,v,r+1,c); dfs(g,v,r-1,c);
dfs(g,v,r,c+1); dfs(g,v,r,c-1);
}
}
Python — DFS with visited set
class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
m, n = len(grid), len(grid[0])
vis, count = set(), 0 def dfs(r: int, c: int) -> None:
if r < 0 or r >= m or c < 0 or c >= n: return if (r,c) in vis or grid[r][c] == '0': return
vis.add((r,c))
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
for r in range(m):
for c in range(n):
if (r,c) not in vis and grid[r][c] == '1':
dfs(r, c); count += 1 return count
| Metric | Value |
|---|---|
| Time | O(m · n) — every cell visited at most once |
| Space | O(m · n) — visited array + O(m · n) call stack worst case |
03
Section Three · Approach 2
In-place Flood Fill — O(m·n) time, O(1) extra space
When a land cell '1' is found, immediately sink the entire island by overwriting every connected land cell with '0'. This marks the island as "counted and processed" without a visited array. The number of times the outer loop triggers a sink equals the number of islands.
💡 Mental model: Imagine you're a cartographer discovering islands in an archipelago. Each time you spot a new island from your ship, you paint all its cells blue (water) on your map as you row ashore and explore every connected piece of land. Then you sail on. The next time you see an unpainted land cell, you know it's a brand-new island you haven't counted yet. The "painting blue" is the in-place
'1' → '0' mutation — no second map needed.
Algorithm — BFS / iterative flood-fill
- Scan all cells in row-major order.
- When
grid[r][c] == '1': increment count, push(r,c)to a queue. - BFS loop: for each cell dequeued, set
grid[r][c] = '0', then enqueue all 4 land neighbors. - Continue outer scan — next island starts when the next unvisited
'1'is encountered.
🎯 When to recognize this pattern:
- "Count connected components in a grid." The signal is a 2D boolean/character grid and the question "how many distinct groups?" Flood-fill from each unvisited component starter directly gives the count.
- Related problems: LC 695 (Max Area of Island — track component size), LC 130 (Surrounded Regions — sink specific components), LC 1020 (Number of Enclaves).
DFS vs BFS for flood fill:
- Both work.
- DFS is simpler to write recursively but risks a stack overflow on very large grids (up to 300×300 = 90,000 cells all land → depth 90,000).
- Iterative BFS avoids the call stack entirely. For interviews, either is acceptable — BFS is safer for production.
04
Section Four · Trace
Visual Walkthrough
Trace on a 4×5 grid with 3 islands. Each BFS call sinks one island.
Number of Islands — BFS Flood-Fill (3 islands)
05
Section Five · Implementation
Code — Java & Python
Java — BFS in-place flood-fill
import java.util.*;
class Solution {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length, count = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == '1') {
count++;
bfs(grid, r, c); // sink the whole island
}
}
}
return count;
}
private void bfs(char[][] grid, int r, int c) {
int m = grid.length, n = grid[0].length;
Queue<int[]> q = new LinkedList<>();
grid[r][c] = '0'; // sink before enqueue — prevent re-entry
q.offer(new int[]{r, c});
while (!q.isEmpty()) {
int[] cell = q.poll();
for (int[] d : DIRS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
grid[nr][nc] = '0'; // sink neighbor before enqueue
q.offer(new int[]{nr, nc});
}
}
}
}
}
Python — BFS in-place flood-fill
from collections import deque
class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
m, n, count = len(grid), len(grid[0]), 0 for r in range(m):
for c in range(n):
if grid[r][c] == '1':
count += 1
grid[r][c] = '0' # sink before enqueue
q = deque([(r, c)])
while q:
cr, cc = q.popleft()
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
nr, nc = cr+dr, cc+dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1':
grid[nr][nc] = '0' # sink neighbor
q.append((nr, nc))
return count
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| DFS with visited array | O(m · n) | O(m · n) | Preserves input but uses extra O(m·n) space |
| Union-Find | O(m · n · α(m·n)) | O(m · n) | Generalizes to dynamic connectivity; heavier constant |
| BFS in-place ← optimal | O(m · n) | O(min(m,n)) queue | Mutates input — confirm with interviewer; otherwise use visited array |
Why O(min(m,n)) queue space?:
- In BFS, the queue holds at most one BFS frontier at a time.
- For a grid, the largest possible frontier is a diagonal wave across the grid — bounded by
min(m, n)cells. - In contrast, a recursive DFS on an all-land grid can go m·n levels deep, overflowing the call stack.
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| All water | All '0' | Outer scan never finds '1'. Returns 0 correctly. |
| All land | All '1' | First cell starts BFS that sinks everything. Returns 1. |
| 1×1 land | [["1"]] | Single-cell island. BFS starts and immediately finishes. Returns 1. |
| 1×n row | [["1","0","1","1"]] | Two islands. BFS for each connected land segment. |
| Large grid (300×300) | All '1' | 90,000 cells — BFS queue approach safe; recursive DFS would overflow the stack. |
| Sinked too late | any | If you set grid[r][c]='0' when dequeuing instead of when enqueuing, the same cell can be enqueued multiple times, causing redundant BFS work. |
⚠ Common Mistake: Sinking the cell after dequeuing instead of before enqueuing. If you enqueue a cell without marking it visited, you can enqueue the same neighbor multiple times before it's dequeued and sunk. Always set
grid[nr][nc] = '0' immediately when enqueuing — this is the standard BFS "mark on enqueue" pattern that prevents duplicate entries.