⚡Flashcard Drill➔
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

  1. This is an Eulerian path in a directed graph, solved by Hierholzer's algorithm.
  2. Sort the adjacency lists in reverse order so pop() yields the lexicographically smallest destination first.
  3. DFS: keep following edges until stuck, then append the node to the route (post-order).
  4. 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 plus pop() 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems