281. Reconstruct Itinerary
You receive tickets, a list of one-way airline tickets, each written as a pair [from, to] of three-letter uppercase airport codes. The whole stack was issued for a single trip that departs from JFK, and each ticket has to be used exactly once.
Rebuild the complete trip and return it as the ordered list of airports visited, beginning with "JFK" — for t tickets, that is t + 1 airport codes.
Several complete trips may exist. Compare candidates airport by airport from the start and return whichever sorts first alphabetically (so at the first point of difference, an itinerary continuing with "DEN" beats one continuing with "DFW"). The input is guaranteed to allow at least one complete trip.
Example 1:
Input: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
Explanation: The tickets chain up in exactly one way once you start at JFK: JFK→MUC, MUC→LHR, LHR→SFO, SFO→SJC.
Example 2:
Input: tickets = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]
Output: ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]
Explanation: Two complete trips exist; ["JFK", "ATL", …] is lexicographically smaller than ["JFK", "SFO", …], so the trip that leaves JFK toward ATL first wins.
Constraints:
- 1 ≤ t ≤ 300
- Every airport code is exactly 3 uppercase English letters
- from ≠ to for every ticket (duplicate tickets may occur)
- At least one complete itinerary using all tickets exists.
Hints:
Model airports as nodes and tickets as directed edges. "Use every ticket exactly once" is precisely an Eulerian path through this multigraph, starting at JFK.
Pure greed fails: always flying to the alphabetically smallest airport can strand you in a dead end while unused tickets remain. One fix is DFS that tries destinations in sorted order and backtracks out of dead ends.
The elegant fix is Hierholzer's algorithm: walk greedily (min-heap per airport) until stuck, and record an airport only when it has no unused tickets left — a postorder. The recorded list, reversed, is the itinerary, and dead ends automatically sink to the end.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Expected output: ["JFK", "MUC", "LHR", "SFO", "SJC"]