DFS
MediumRecurse into unvisited neighbours
Problem
Perform a depth-first traversal of a graph, marking visited nodes to avoid revisiting.
Follow one path as far as it goes, then back up and try the next.
The idea
Mark the current vertex visited, then recurse into every neighbour not yet seen. The visited set is not an optimisation here — without it any cycle makes the traversal run forever.
The trick
- Mark visited on entry, before recursing.
- Loop over all vertices at the top level to cover a disconnected graph.
- O(V + E) time, O(V) space.
1
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1
Step 1 of 9. Scan for land. Each unvisited '1' starts a new island; flood-fill its whole blob so it isn't counted twice.
1/9
Optimal
timeO(rows·cols)spaceO(rows·cols)
Sink each island you find.
1for (r, c) if (grid[r][c] === '1') {2 islands++;3 sink(r, c); // DFS marks the blob as water4}5function sink(r, c) {6 if (out of bounds || grid[r][c] !== '1') return;7 grid[r][c] = '0';8 for (const [dr, dc] of DIRS) sink(r+dr, c+dc);9}Input
- grid
- 4 × 4
Memory
- at
- —
- cells marked
- 0
Output
- islands
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- adjList
- Output:
- DFS order
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.