Interview preparation
Number of Islands
1Problem statement
Given an m × n grid of '1' (land) and '0' (water), return the number of islands. An island is a group of land cells connected horizontally or vertically, surrounded by water.
2Examples
3Constraints
- 1 ≤ m, n ≤ 300
- grid[i][j] is '0' or '1'.
4Approaches
Approach 1
Brute Force
For every land cell, run a full search to collect its island and compare sets to avoid double counting.
Approach 2
Better: Union-Find
Union adjacent land cells; count distinct roots.
Approach 3
Optimal: BFS / DFS flood fill
Scan the grid; each unvisited land cell starts a new island and a BFS that sinks (marks) every connected land cell.
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
function numIslands(rows) {
const grid = rows.map((r) => r.split(""));
const R = grid.length;
const C = grid[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let islands = 0;
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (grid[r][c] !== "1") continue;
islands++;
grid[r][c] = "0";
const queue = [[r, c]];
for (let head = 0; head < queue.length; head++) {
const [cr, cc] = queue[head];
for (const [dr, dc] of dirs) {
const nr = cr + dr;
const nc = cc + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === "1") {
grid[nr][nc] = "0";
queue.push([nr, nc]);
}
}
}
}
}
return islands;
}
console.log(numIslands(["11110", "11010", "11000", "00000"]));
console.log(numIslands(["11000", "11000", "00100", "00011"]));
6Complexity
Time
O(m·n)
Space
O(m·n) worst case
7Visual walkthrough
- 1.Treat each land cell as a vertex and each up/down/left/right land neighbour as an edge.
- 2.Each BFS from a new land cell explores exactly one connected component.
- 3.The number of BFS starts is the number of islands.
Related visualization (Graph BFS (Breadth-First Search)) — shows the core data-structure operations this solution relies on:
Queue (front → rear)
Traversal order
Explores the graph level by level using a queue. Because vertices are discovered in order of distance, BFS also finds the shortest path (fewest edges) from the start in an unweighted graph.