Reconstruct Itinerary
Problem
Given a list of airline tickets [from, to], return the itinerary that uses every ticket exactly once and starts at "JFK". If multiple valid itineraries exist, return the one with the smallest lexical order.
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]["JFK","MUC","LHR","SFO","SJC"]def find_itinerary(tickets):
from collections import defaultdict
import heapq
g = defaultdict(list)
for a, b in tickets: heapq.heappush(g[a], b)
route = []
def dfs(u):
while g[u]:
dfs(heapq.heappop(g[u]))
route.append(u)
dfs("JFK")
return route[::-1]function findItinerary(tickets) {
const g = {};
for (const [a, b] of tickets) (g[a] = g[a] || []).push(b);
for (const k in g) g[k].sort();
const route = [];
function dfs(u) {
const list = g[u] || [];
while (list.length) dfs(list.shift());
route.push(u);
}
dfs("JFK");
return route.reverse();
}class Solution {
Map<String, PriorityQueue<String>> g = new HashMap<>();
LinkedList<String> route = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
for (var t : tickets) g.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).add(t.get(1));
dfs("JFK");
return route;
}
void dfs(String u) {
PriorityQueue<String> pq = g.get(u);
while (pq != null && !pq.isEmpty()) dfs(pq.poll());
route.addFirst(u);
}
}unordered_map<string, multiset<string>> g;
vector<string> route;
void dfs(const string& u) {
auto& s = g[u];
while (!s.empty()) {
string v = *s.begin();
s.erase(s.begin());
dfs(v);
}
route.push_back(u);
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
for (auto& t : tickets) g[t[0]].insert(t[1]);
dfs("JFK");
reverse(route.begin(), route.end());
return route;
}Explanation
This is an Eulerian path problem — we must use every ticket (edge) exactly once. The neat solution is Hierholzer's algorithm: a DFS that only records an airport after all of its outgoing flights are used up, then we reverse the result.
To get the smallest lexical itinerary, we keep each airport's destinations sorted (a heap in Python, a sorted list in JS). The DFS always flies to the alphabetically smallest unused destination first.
The clever part is the post-order: route.append(u) happens only after while g[u] has drained every edge out of u. An airport with no way out becomes a "dead end" and is added first, so dead ends pile up at the front of route. Reversing at the end (route[::-1]) flips them into the correct visiting order.
This naturally handles the tricky case where greedily picking the smallest city would otherwise strand you, because stranded airports are appended early and end up last.
Example: tickets [[MUC,LHR],[JFK,MUC],[SFO,SJC],[LHR,SFO]]. DFS from JFK drains the single chain, appends in reverse, and reversing gives [JFK, MUC, LHR, SFO, SJC].