Reconstruct Itinerary
hardTime: O(E log E)Space: O(V+E)
Recognize the pattern
use all tickets exactly oncefind Eulerian pathlexicographically smallest itinerary
Brute force idea
Try all permutations of tickets — O(n!). Each ordering checked for validity.
Better approach
Hierholzer's algorithm: DFS greedily choosing the lexicographically smallest neighbor. When stuck, add the current airport to the result in reverse. O(E log E) for sorting adjacency lists.
Key invariant
By always choosing the smallest destination and building the result when backtracking (stuck = no more edges), you construct the lexicographically smallest Eulerian path in reverse.
Watch out for
Not building the result in reverse — Hierholzer's adds cities when backtracking from dead ends, so the path is assembled from the end backward.