DSA problem

Reconstruct Itinerary

HardEulerian CircuitPattern: Eulerian Circuittop300FreeAmazonGoogleMicrosoftBloombergApple

You are given a list of airline tickets where tickets[i] = [fromi, toi] represents 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", thus 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.

This problem is a textbook application of an Eulerian path on a directed multigraph. Each ticket is a directed edge that must be used exactly once, and we are looking for a single walk that traverses every edge exactly once — starting at the fixed vertex "JFK". Because the input guarantees at least one valid itinerary exists, the graph admits an Eulerian path that begins at "JFK".

A greedy "always pick the smallest neighbor" approach fails: choosing the lexicographically smallest next airport can strand you in a dead-end before all edges are used. The fix is Hierholzer's algorithm, which performs a depth-first walk that consumes edges as it traverses them and only commits a vertex to the answer after every outgoing edge has been exhausted.

The optimal approach builds an adjacency list where each source maps to a min-heap of destinations, then runs an iterative DFS from "JFK". Each step pops the smallest available neighbor from the current vertex's heap and descends; when a vertex has no more outgoing edges, it is pushed onto a result stack. Reversing the stack at the end yields the lexicographically smallest Eulerian path. The algorithm runs in O(E log E) time and O(V + E) space, where E is the number of tickets.

Examples

Example 1

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output: ["JFK","MUC","LHR","SFO","SJC"]

Explanation: There is exactly one valid Eulerian path starting at JFK, and it consumes all four tickets in this order.

Example 2

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]

Explanation: Two itineraries are possible; the lexicographically smaller one chooses ATL before SFO at the first step.

Example 3

Input: tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]

Output: ["JFK","NRT","JFK","KUL"]

Explanation: A naive greedy walk to KUL first would strand us — Hierholzer's post-order push correctly defers KUL until the end.

Constraints

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3 and toi.length == 3
fromi and toi consist of uppercase English letters.
All the tickets form at least one valid itinerary starting from "JFK".

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

grapheulerian-pathhierholzerdfsheap

Browse all DSA problems