Reconstruct Itinerary
The briefingthe full drill, in my own words
The drill: Rebuild a single trip from JFK that uses every ticket in the pile exactly once. When more than one full itinerary is possible, the one that reads smallest airport-code-first wins.
A pile of one-way airline tickets arrives, each naming a departure airport and an arrival airport. Every one of those tickets has to be used exactly once, the trip has to start at JFK, and it has to use up the entire pile.
More than one itinerary can satisfy that — the tie gets broken by reading order: whichever valid full itinerary comes first alphabetically, city code by city code, is the one to hand back.
This input always admits at least one itinerary that uses every ticket, so the only work is finding the lexicographically smallest one, not proving one exists.
- ticket count is small, at most a few hundred
- airport codes are three uppercase letters
- duplicate tickets between the same pair of airports are allowed
- trip always starts at JFK and must use every ticket exactly once
- tie-break: the itinerary that sorts smallest airport-code-first wins
The hintstake only what you need
HINT 1 THE NUDGE
This is a path that must consume every edge of a graph exactly once — not a shortest path, and not a search for any valid order, but the one specific order that sorts first.
HINT 2 THE STRUCTURE
Greedily taking the alphabetically smallest next city can strand you at a dead end with unused tickets still in hand. What lets a route recover from a wrong early choice?
HINT 3 ONE STEP FROM THE ANSWER
Hierholzer's trick: recurse into the smallest unused destination first, and only append a city to the itinerary once it has no departures left. That post-order, reversed, is the answer — dead ends naturally settle to the end.
Coach's boardthe pattern, step by step
Sort each city's destinations so the smallest lexical option is tried first. Hierholzer's DFS starts at JFK.
The splitstwo paces, two languages
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = collections.defaultdict(list)
for src, dst in sorted(tickets, reverse=True):
graph[src].append(dst)
route = []
def visit(city):
while graph[city]:
visit(graph[city].pop())
route.append(city)
visit("JFK")
return route[::-1]class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
n = len(tickets)
graph = collections.defaultdict(list)
for src, dst in tickets:
graph[src].append(dst)
for city in graph:
graph[city].sort()
used = {city: [False] * len(dsts) for city, dsts in graph.items()}
route = ["JFK"]
def backtrack(city):
if len(route) == n + 1:
return True
if city not in graph:
return False
for i, dst in enumerate(graph[city]):
if not used[city][i]:
used[city][i] = True
route.append(dst)
if backtrack(dst):
return True
route.pop()
used[city][i] = False
return False
backtrack("JFK")
return routeclass Solution {
private Map<String, PriorityQueue<String>> graph;
private LinkedList<String> route;
public List<String> findItinerary(String[][] tickets) {
graph = new HashMap<>();
for (String[] t : tickets) {
graph.computeIfAbsent(t[0], x -> new PriorityQueue<>()).add(t[1]);
}
route = new LinkedList<>();
visit("JFK");
Collections.reverse(route);
return route;
}
private void visit(String city) {
PriorityQueue<String> dsts = graph.get(city);
while (dsts != null && !dsts.isEmpty()) {
visit(dsts.poll());
}
route.add(city);
}
}class Solution {
private List<String> route;
private int n;
private Map<String, List<String>> graph;
private Map<String, boolean[]> used;
public List<String> findItinerary(String[][] tickets) {
n = tickets.length;
graph = new HashMap<>();
for (String[] t : tickets) {
graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(t[1]);
}
for (List<String> dsts : graph.values()) Collections.sort(dsts);
used = new HashMap<>();
for (Map.Entry<String, List<String>> e : graph.entrySet()) {
used.put(e.getKey(), new boolean[e.getValue().size()]);
}
route = new ArrayList<>();
route.add("JFK");
backtrack("JFK");
return route;
}
private boolean backtrack(String city) {
if (route.size() == n + 1) return true;
List<String> dsts = graph.get(city);
if (dsts == null) return false;
boolean[] flags = used.get(city);
for (int i = 0; i < dsts.size(); i++) {
if (!flags[i]) {
flags[i] = true;
route.add(dsts.get(i));
if (backtrack(dsts.get(i))) return true;
route.remove(route.size() - 1);
flags[i] = false;
}
}
return false;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED