Mediumgrid-graph-bfs
Number of Islands
Problem (restated)
Given a 2D grid of ‘1’ (land) and ‘0’ (water), return the number of islands. An island is max 4-directionally connected land.
Intuition
Each unvisited land cell starts a component. Flood-fill (DFS/BFS) marks the whole island; count how many times you start a fill.
Approaches
DFS flood fill
Tested onlyTime O(m·n)Space O(m·n) worst-case stack
Idea. Iterate cells; on land, increment count and DFS to mark all connected land as water/visited.
Walkthrough. Grid with two separate land blobs → count 2.
Trade-offs. DFS is concise; BFS uses explicit queue (safer stack depth on huge grids).
Solution
export function numIslands(grid: string[][]): number {
if (!grid.length) return 0;
const m = grid.length, n = grid[0]!.length;
const dfs = (r: number, c: number) => {
if (r < 0 || c < 0 || r >= m || 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);
};
let count = 0;
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;
}
export function numIslands(grid: string[][]): number {
if (!grid.length) return 0;
const m = grid.length, n = grid[0]!.length;
const dfs = (r: number, c: number) => {
if (r < 0 || c < 0 || r >= m || 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);
};
let count = 0;
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;
}
Template connection
Grid BFS/DFS connected components.
Reflection
- Which pattern gave this away within 90 seconds?
- What changed from the standard template?
- What would break the current solution?