Easy difficulty · Algorithm · Topics: graph, adjacency-list, representation
An adjacency list stores a graph as an array with one entry per vertex: adj[u] is the list of vertices you can reach from u in one step. The task is to build that structure from a list of edges, for a directed or an undirected graph.
Think of a phone contacts app: each person stores only the numbers of the people they actually know, not a blank slot for every other person on Earth. The adjacency list does the same, so it uses memory proportional to the number of vertices plus the number of real edges.
The invariant is simple: v appears in adj[u] exactly when the edge u -> v exists. For an undirected edge u - v that means both adj[u] contains v and adj[v] contains u.
adj with n empty lists, one per vertex.[u, v], push v onto adj[u].u onto adj[v].adj. Neighbours appear in the order the edges were given.Test case 0: n = 4, edges [[0,1], [0,2], [1,2], [2,3]], undirected.
| Edge | Lists changed | adj after the step |
|---|---|---|
| start | none | [[], [], [], []] |
[0,1] | adj[0], adj[1] | [[1], [0], [], []] |
[0,2] | adj[0], adj[2] | [[1,2], [0], [0], []] |
[1,2] | adj[1], adj[2] | [[1,2], [0,2], [0,1], []] |
[2,3] | adj[2], adj[3] | [[1,2], [0,2], [0,1,3], [2]] |
| Time | Space | Reason | |
|---|---|---|---|
| Build | O(n + E) | O(n + E) | One list per vertex, then each edge adds one or two entries. |
Edge lookup u -> v | O(deg(u)) | - | The list of u must be scanned (O(1) if you use a Set per vertex). |
List all neighbours of u | O(deg(u)) | - | Exactly the neighbours, nothing else is touched. |
adj[u].push([v, weight]).new Array(n).fill([]), which makes every vertex share one list. Use Array.from with a function.0..n-1 need a map from label to index first.Follow adj: the node-link view grows one edge at a time as adj[u].push(v) runs. Watch u and v mark the current edge, and notice how each undirected edge appears under both endpoints, so every list length equals the degree of its vertex.
Input: n = 4, edges = [[0, 1], [0, 2], [1, 2], [2, 3]], directed = false
Output: [[1, 2], [0, 2], [0, 1, 3], [2]]
class Solution {
buildList(n, edges, directed) {
// one (initially empty) neighbour list per vertex
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
if (!directed) {
adj[v].push(u); // an undirected edge is listed under both endpoints
}
}
return adj;
}
}