Matrices
MediumA grid is a graph with implicit edges
Problem
Learn grid DFS: treat each cell as a node connected to its 4 neighbours, marking visited cells to avoid loops.
Flood through connected cells, coloring them visited as you go.
The idea
Treat each cell as a node whose neighbours are the four (or eight) adjacent cells, so no adjacency list is needed — the edges are implied by the coordinates. Every graph traversal then applies directly to grids.
The trick
- Direction arrays like [[1,0],[-1,0],[0,1],[0,-1]] keep the loop clean.
- Bounds-check before reading, or you will index outside the grid.
- Marking the grid itself avoids a separate visited structure.
1
1
0
1
1
0
0
0
0
0
1
1
Step 1 of 8. Scan for land (1). Each new blob is one island — DFS sinks its whole region.
1/8
Optimal
timeO(rows·cols)spaceO(rows·cols)
Depth-first sink.
1function sink(r, c) {2 if (oob(r,c) || grid[r][c] !== '1') return;3 grid[r][c] = '0';4 sink(r+1,c); sink(r-1,c); sink(r,c+1); sink(r,c-1);5}Input
- grid
- 3 × 4
Memory
- at
- —
- cells marked
- 0
Output
- islands
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- count islands
- Output:
- components of 1s
Finished the walkthrough? Add it to your streak.