Reconstruct Itinerary
You're given a list of airline tickets, each a pair [from, to] of airport codes. All the tickets belong to one traveler whose trip starts at "JFK". Use every ticket exactly once and return the airports in the order visited. If several itineraries work, return the one that is smallest in lexical order, comparing airports one at a time. At least one valid itinerary exists.
Examples
tickets = [["JFK","SEA"],["SEA","DEN"],["DEN","BOS"]] returns ["JFK","SEA","DEN","BOS"]
Only one ticket leaves each airport, so the route is forced.
tickets = [["JFK","AUS"],["JFK","LAX"],["LAX","JFK"]] returns ["JFK","LAX","JFK","AUS"]
AUS sorts first, but flying there first strands the other two tickets. The only itinerary that uses every ticket visits LAX first and ends at AUS.
tickets = [["JFK","ORD"],["ORD","JFK"],["JFK","DFW"],["DFW","JFK"]] returns ["JFK","DFW","JFK","ORD","JFK"]
Both round trips can go in either order, so the smaller code, DFW, comes first.
Constraints
- 1 <= tickets.length <= 300
- tickets[i].length == 2
- Each airport code is three uppercase English letters.
- At least one itinerary uses every ticket.
Hints
Each ticket is a directed edge, and you must use every edge exactly once. What kind of path is that?
It's an Eulerian path from JFK. Picking the smallest destination first is right, as long as a dead end ends up at the end of the itinerary.
Keep each airport's destinations in a min-heap or sorted list. Use a stack starting at JFK: while the top has tickets left, push its smallest destination; otherwise pop the top onto the route. Reverse the route.
Drill This: Your Approach First
Approach
Treat airports as nodes and tickets as directed edges. An itinerary that uses every ticket once is an Eulerian path from JFK, and Hierholzer's algorithm finds one. Sort each airport's destinations so the smallest is taken first, and walk with an explicit stack: while the airport on top still has an unused ticket, take its smallest destination and push it. When the top airport has no tickets left, pop it onto the route. A dead end is popped before the airports that lead to it, so it lands at the end of the trip, and reversing the route gives the itinerary. O(E log E) time for E tickets, dominated by the sort, and O(E) space.
Time
O(E log E)
Space
O(E)
Pitfall
Solutions
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, PriorityQueue<String>> graph = new HashMap<>();
for (List<String> t : tickets) {
graph.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).add(t.get(1));
}
LinkedList<String> route = new LinkedList<>();
Deque<String> stack = new ArrayDeque<>();
stack.push("JFK");
while (!stack.isEmpty()) {
PriorityQueue<String> next = graph.get(stack.peek());
if (next != null && !next.isEmpty()) {
stack.push(next.poll());
} else {
route.addFirst(stack.pop());
}
}
return route;
}
}from collections import defaultdict
class Solution:
def findItinerary(self, tickets):
graph = defaultdict(list)
# Reverse-sorted lists, so pop() returns the smallest destination.
for src, dst in sorted(tickets, reverse=True):
graph[src].append(dst)
route, stack = [], ["JFK"]
while stack:
if graph[stack[-1]]:
stack.append(graph[stack[-1]].pop())
else:
route.append(stack.pop())
return route[::-1]