Adjacency List
MediumEach node keeps a list of its neighbours
Problem
Represent a graph as an adjacency list: for each node, a list of its neighbours.
Give every node a little list of who it's connected to.
The idea
Storing neighbours per node uses O(V + E) memory and lets you iterate a node's edges directly, which is what almost every traversal needs. A matrix costs O(V²) and is only preferable when edge lookups dominate and the graph is dense.
The trick
- List: O(V+E) space, O(degree) to iterate a node's edges.
- Matrix: O(V²) space, O(1) to test whether a specific edge exists.
- Undirected edges must be added in both directions.
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:
- edges [[0,1],[0,2]]
- Output:
- 0:[1,2], 1:[0], 2:[0]
Finished the walkthrough? Add it to your streak.