Graphs
Drop ink on any land square you have not coloured yet. It spreads to every square joined to it, but never crosses water. Each drop is one island, and counting the drops counts the islands.
2 · Watch
No sound? Captions are on by default.
3 · Now you drive
Keys:←→ stepSpace playR reset
Number of Islands
or try
1–5 rows of 1s (land) and 0s (water), up to 6 wide, rows separated by spaces.Scan the grid row by row. No islands yet.Step 1 of 12. 4 rows, 5 columns, 7 land cells. Scanning row by row. No islands yet.
Step 1 of 12
solution.ts▶ marks the line running now
function numIslands(grid: string[][]): number {
let islands = 0;
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] !== "1") continue;
islands++;
grid[r][c] = "0";
const queue: [number, number][] = [[r, c]];
while (queue.length > 0) {
const [cr, cc] = queue.shift()!;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = cr + dr, nc = cc + dc;
if (grid[nr]?.[nc] === "1") {
grid[nr][nc] = "0";
queue.push([nr, nc]);
}
}
}
}
}
return islands;
}
4 · Your turn
0 of 6 problems solved
- Medium01
Number of Islands
The one you just watched. Write it from memory.
- Medium02
Clone Graph
Same flood, but copy each node as you claim it.
- Medium03
Pacific Atlantic Water Flow
Flood from both oceans, keep the overlap.
- Medium04
Course Schedule
Flood along arrows; a loop means no schedule.
- Medium05
Number of Connected Components in an Undirected Graph
LeetCode PremiumCount the floods in a graph, not a grid.
- Medium06
Graph Valid Tree
LeetCode PremiumOne flood plus no loops means a tree.