HardPro challengePythonJavaScriptTypeScript
Graph — Reconstruct Itinerary
Data StructuresGraphsDFSEuler Path
solve(tickets) — tickets[i] = [from, to] are airline tickets. Rebuild the
itinerary that starts at "JFK" and uses every ticket exactly once. If several
itineraries exist, return the one with the smallest lexical order (compare
airport codes as strings, position by position). A valid itinerary is guaranteed to
exist.
This is an Eulerian path problem. Hierholzer's algorithm solves it: do a DFS
that always takes the smallest unused destination, add an airport to the route when
it has no unused tickets left (post-order), and reverse the route at the end.
Examples
solve([["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]])
→ ["JFK","MUC","LHR","SFO","SJC"]
solve([["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]])
→ ["JFK","ATL","JFK","SFO","ATL","SFO"]
solve([["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]])
→ ["JFK","NRT","JFK","KUL"]Sample tests
Test #1A single path
Input: [[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Test #2Cycles through JFK
Input: [[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Test #3The smaller destination is a dead end — must go last
Input: [[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]]
Output: ["JFK","NRT","JFK","KUL"]