The problem
Each ticket [from, to] is one flight. Starting at "JFK", use every ticket exactly once and return the airports in the order visited.
If several itineraries use every ticket, return the one that comes first alphabetically when read as a list of airports. At least one exists.
Examples
- Input
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
- Output
["JFK", "MUC", "LHR", "SFO", "SJC"]
- Input
tickets = [ ["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"] ]
- Output
["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]
Constraints
- 1 ≤ tickets.length ≤ 300
- Airports are three uppercase letters.
- A ticket never goes from an airport to itself.
The idea
A route using every edge exactly once is an Eulerian path. Greedily taking the alphabetically first flight each time can strand you: fly JFK → KUL first, and the ticket NRT → JFK is never used.
Hierholzer’s algorithm fixes this by building the route backwards. Always take the smallest remaining flight. When you land somewhere with no tickets left, that airport must be the end of whatever is still unwritten — so write it down (at the back) and step back to try from the previous airport. Reversed at the end, the written list is the itinerary.
- Time
- O(E log E) — sorting the E tickets; the walk itself is O(E)
- Space
- O(E)
Solution · every language run against every case
class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: out_of = defaultdict(list) # airport -> destinations still to fly to for a, b in sorted(tickets, reverse=True): out_of[a].append(b) # reverse order, so popping gives the smallest first # Hierholzer's algorithm: fly on while tickets remain; an airport with none left # is where the route ends, so it is written down last-first. route, stack = [], ["JFK"] while stack: if out_of[stack[-1]]: stack.append(out_of[stack[-1]].pop()) else: route.append(stack.pop()) return route[::-1]