Adjacency Lists to Edge List
EasyGraphs
Problem
A mapping tool stores an undirected road map as adjacency lists: adj[i] lists the junctions directly connected to junction i, in no particular order. Whenever j appears in adj[i], i appears in adj[j].
Export a copy of the map as an edge list. List every road exactly once as [u, v] with u < v, and sort the edges by u, then by v.
Example 1
- Input:
- adj = [[1, 2], [0, 2], [1, 0]]
- Output:
- [[0, 1], [0, 2], [1, 2]]
A triangle: each of its three roads appears once.
Example 2
- Input:
- adj = [[3], [], [3], [2, 0]]
- Output:
- [[0, 3], [2, 3]]
Junction 1 has no roads.
Example 3
- Input:
- adj = [[]]
- Output:
- []
Constraints
- 1 ≤ adj.length ≤ 10^5
- Total entries ≤ 2·10^5
- No self-loops or repeated neighbours; the lists are symmetric.
Hint
Show the first hint
Every road appears twice in the adjacency lists. How do you keep exactly one copy?
Walkthrough
How to approach it
01Clarify before coding
- Are the input lists sorted? No, neighbours come in any order.
- Should isolated junctions appear? No, an edge list only contains roads.
- Is the map guaranteed symmetric? Yes, so each road is seen exactly twice.
02Brute force
Collect every pair [min, max] from every list, put them in a set to remove duplicates, then sort.
Cost: O(m log m) time and extra hashing; correct, but the sort is avoidable.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.