Reconstruct Itinerary

Difficulty: Hard Source: NeetCode

Problem

You are given a list of airline tickets represented by pairs of departure and arrival airports [from, to]. Reconstruct the itinerary in order. All of the tickets must be used once and the itinerary must begin with "JFK".

If there are multiple valid itineraries, return the one with the smallest lexicographic order when read as a single string.

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"]

Constraints:

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• tickets[i][0], tickets[i][1] consist of uppercase English letters
• All tickets form at least one valid itinerary

Prerequisites

Before attempting this problem, you should be comfortable with:

• Eulerian Path — a path in a graph that visits every edge exactly once
• Hierholzer’s Algorithm — efficient algorithm for finding Eulerian paths
• DFS on a Graph — depth-first traversal used to build the path

1. Brute Force (Backtracking)

Intuition

Try all possible orderings of tickets using backtracking. Start from JFK, try each unused ticket from the current airport, recurse, and backtrack if we get stuck. Among all valid complete itineraries, return the lexicographically smallest. This works but is very slow because there are up to n! orderings to explore.

Algorithm

1. Sort tickets so destinations are in lexicographic order.
2. Use DFS/backtracking from “JFK”, marking tickets as used.
3. If all tickets are used, record the itinerary.
4. Return the lexicographically smallest result.

Solution

def findItinerary_brute(tickets):
    from collections import defaultdict
    tickets.sort()
    graph = defaultdict(list)
    for src, dst in tickets:
        graph[src].append(dst)

    result = []
    path = ["JFK"]

    def backtrack():
        if len(path) == len(tickets) + 1:
            result.append(path[:])
            return True
        src = path[-1]
        for i, dst in enumerate(graph[src]):
            if dst is not None:
                graph[src][i] = None  # mark used
                path.append(dst)
                if backtrack():
                    return True
                path.pop()
                graph[src][i] = dst  # restore
        return False

    backtrack()
    return result[0] if result else []


t1 = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
print(findItinerary_brute(t1))  # ["JFK","MUC","LHR","SFO","SJC"]

t2 = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
print(findItinerary_brute(t2))  # ["JFK","ATL","JFK","SFO","ATL","SFO"]

Complexity

• Time: O(n! * n) worst case — exponential backtracking
• Space: O(n) — recursion depth

2. Hierholzer’s Algorithm (Eulerian Path)

Intuition

This problem is asking for an Eulerian path — a path that visits every edge (ticket) exactly once. Hierholzer’s algorithm finds Eulerian paths efficiently. The key insight is: do a DFS, and only add a node to the result after all its outgoing edges have been explored. This “post-order” addition produces the itinerary in reverse.

Why does this work? If we hit a dead end early (used all edges from a node), that node must come later in the final itinerary (or be the last stop). By reversing the post-order result, we get the correct forward itinerary.

To guarantee lexicographic order, sort the adjacency lists in reverse so we can use pop() from the end (which removes the smallest element).

Algorithm

1. Build the adjacency list, sorting destinations in reverse order.
2. Start DFS from “JFK”.
3. While there are unvisited destinations from the current node, pop the next destination and recurse.
4. After all neighbors are exhausted, append the current node to the result.
5. Reverse the result at the end.

Solution

from collections import defaultdict

def findItinerary(tickets):
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)
    # Sorted in reverse so pop() gives lexicographically smallest first

    result = []

    def dfs(node):
        while graph[node]:
            next_node = graph[node].pop()
            dfs(next_node)
        result.append(node)

    dfs("JFK")
    return result[::-1]


t1 = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
print(findItinerary(t1))  # ["JFK","MUC","LHR","SFO","SJC"]

t2 = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
print(findItinerary(t2))  # ["JFK","ATL","JFK","SFO","ATL","SFO"]

t3 = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
print(findItinerary(t3))  # ["JFK","NRT","JFK","KUL"]

Complexity

• Time: O(E log E) — sorting the edges; DFS visits each edge once
• Space: O(E) — adjacency list and result

Common Pitfalls

Adding nodes to result too early. If you add a node when you first visit it (pre-order), you’ll get the wrong answer. The key to Hierholzer’s is post-order: only add a node after all its edges are used up.

Forgetting to reverse the result. Post-order DFS builds the path backwards. Always reverse before returning.

Not sorting in reverse before using pop(). Python’s list.pop() removes from the end. If you sort ascending and pop from the end, you get the largest element — the opposite of what you want. Sort in reverse so pop() gives the lexicographically smallest.