Reconstruct Itinerary
Reconstruct the lexicographically smallest itinerary using all tickets exactly once.
Try it
Step through the core mechanic. The simulator below runs the advanced graph shape this problem is built on.
No dedicated step-through for this one yet. The shape is Advanced graph — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
This is an Eulerian path. Hierholzer's algorithm: DFS following edges in lexical order, deleting each as used, and prepend a node to the route once it has no remaining edges. Reverse for the final order.
| Aspect | Value |
|---|---|
| Pattern | Advanced graph |
| Recognise it by | Use every edge once — Eulerian path (Hierholzer). |
| Time complexity | O(E log E) |
| Space complexity | O(E) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.