NeetCode #629LC-332HardAdvanced GraphsNC 150NC 250
← Back to All Problems#629 · #332 · Reconstruct Itinerary(重新安排行程)
📌 Problem Statement & Constraints
You are given a list of airline
tickets where tickets[i] = [from, to]. Reconstruct the itinerary in order, starting from "JFK", using all tickets exactly once. If several valid itineraries exist, return the lexicographically smallest. Constraints: 1 <= tickets.length <= 300; the input is guaranteed to have at least one valid itinerary.💡 Core Algorithmic Approaches
- This is an Eulerian path in a directed graph, solved by Hierholzer's algorithm.
- Sort the adjacency lists in reverse order so
pop()yields the lexicographically smallest destination first. - DFS: keep following edges until stuck, then append the node to the route (post-order).
- Reversing the post-order route gives the itinerary.
💻 Benchmark Python3 Implementation
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
from collections import defaultdict
g = defaultdict(list)
# reverse-sorted so pop() gives the smallest destination first
for a, b in sorted(tickets, reverse=True):
g[a].append(b)
route = []
def dfs(node: str) -> None:
while g[node]:
dfs(g[node].pop()) # greedy: smallest destination next
route.append(node) # post-order -> appended when stuck
dfs("JFK")
return route[::-1] # reverse the post-order⚡ Complexity Deep Dive
⏱️ Time Complexity
O(E log E): the sort of the tickets dominates.
💾 Space Complexity
O(E) for the graph and the route.
⚠️ Interview Pitfalls & Follow-ups
- Sorting ascending and using
pop(0):pop(0)is O(n); reverse-sorting pluspop()is O(1). - Appending before recursing (pre-order): the route must be built post-order.
- Forgetting to reverse at the end: Hierholzer produces the route backwards.
- Using a simple greedy without backtracking: a dead end can force a revisit of earlier choices.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.