Reconstruct Itinerary

The key idea

Every ticket must be used exactly once, so the itinerary is an Eulerian path over the airport graph. Greedily walking the smallest-lexical edge first can strand you in a dead end before using every ticket. Hierholzer's algorithm fixes this: when a node has no unused outgoing edges, append it to the route, then reverse the route at the end. The dead-end node correctly lands last.

Problem

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from JFK, so the itinerary must begin with JFK. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"]. You may assume all tickets form at least one valid itinerary, and all tickets must be used once and only once.

Constraints

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi and toi consist of uppercase English letters
fromi != toi

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"]

Complexity

Time: O(E log E) Space: O(E)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →