LeetEye LeetEye
Hard Advanced Graphs ~5 min

Reconstruct Itinerary

advanced-graphs reconstruct-itinerary

Problem

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and arrival airports of one flight. Reconstruct the itinerary in order and return it.

All the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, return the itinerary that has the smallest lexical order when read as a single string.

You must use all the tickets once and only once.

Examples

Example 1
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Example 2
Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Another valid itinerary is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it's lexicographically larger.
Key Insight

Hierholzer's algorithm: DFS with post-order collection. Visit neighbors in sorted order for lexicographic result.

Eulerian path with Hierholzer's: DFS with post-order collection (add node after visiting all edges). Process neighbors in sorted order. Reverse result at end.

How to Approach This Problem

Pattern Recognition: When you see keywords like reconstruct itinerary advanced-graphs, think Advanced Graphs.

Step-by-Step Reasoning

1 Using every ticket (edge) exactly once is:
Answer: Eulerian path (every edge once)
We must traverse every edge (ticket) exactly once.
2 Simple DFS from JFK might fail because:
Answer: Can get stuck before using all tickets
Greedy DFS might take a path that doesn't use all edges. Need to backtrack or use Hierholzer's.
3 Hierholzer's algorithm:
Answer: Post-order collection + reverse
Add node to path AFTER visiting all its neighbors. Reverse at end. Handles dead-ends correctly.
4 To ensure smallest lexical order:
Answer: Visit neighbors in sorted order
Process neighbors in sorted order, so we always try the lexicographically smaller option first.
5 Adding to result after all neighbors are processed:
Answer: Ensures we use all edges before finalizing
A node only gets added when all its outgoing edges are used. Dead-ends added first, start added last, then reverse.

Solution

from collections import defaultdict

def findItinerary(tickets: List[List[str]]) -> List[str]:
    # Build adjacency list with sorted destinations
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)
    
    result = []
    
    def dfs(airport):
        while graph[airport]:
            # Pop from end (smallest lexicographically due to reverse sort)
            next_airport = graph[airport].pop()
            dfs(next_airport)
        result.append(airport)  # Post-order
    
    dfs("JFK")
    
    return result[::-1]  # Reverse for correct order

Complexity Analysis

Time O(E log E)
Space O(E)

Master This Pattern

Build intuition with interactive MCQs. Practice Advanced Graphs problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye