LeetCode 332: Reconstruct Itinerary

Problem Restatement

We are given a list of airline tickets.

Each ticket is a pair:

[from, to]

meaning there is a flight from airport from to airport to.

We need to reconstruct the itinerary in order.

Rules:

This is a directed graph problem. Airports are nodes, and tickets are directed edges. We need a path that uses every edge exactly once. That is an Eulerian path problem.

Input and Output

Function shape:

def findItinerary(tickets: list[list[str]]) -> list[str]:
    ...

Examples

Example 1:

Input:
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output:
["JFK","MUC","LHR","SFO","SJC"]

There is only one natural chain:

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 "ATL" comes before "SFO", so the required answer starts:

JFK -> ATL

First Thought: Backtracking

A direct method is to try every possible route.

From the current airport:

1. Choose one unused outgoing ticket.
2. Move to its destination.
3. Continue recursively.
4. If stuck before using all tickets, undo the choice and try another ticket.

To get the lexicographically smallest itinerary, we would try destinations in sorted order.

This works, but it can be expensive because the search may branch many times.

There is a stronger structure here: we are not looking for any ordinary path. We need to use every directed edge exactly once.

That lets us use Hierholzer’s algorithm.

Key Insight

The tickets form a directed multigraph.

We need an itinerary that:

starts at JFK and uses every directed edge exactly once

This is exactly an Eulerian path.

Hierholzer’s algorithm builds the path by walking edges until it reaches a node with no unused outgoing edges. That node is then added to the answer after all its outgoing edges are consumed.

This gives a postorder DFS:

while current airport has unused outgoing flights:
    take one flight and DFS from the destination

add current airport to answer

The answer is built backward, so we reverse it at the end.

For lexicographic order, we need to consume the smallest destination first. In Python, an efficient trick is:

1. Sort tickets in reverse lexicographic order.
2. Push destinations into adjacency lists.
3. Use pop() to remove the last destination.

Because the list is reversed, pop() gives the smallest available destination.

Algorithm

Build a graph:

from_airport -> list of destination airports

Sort tickets in reverse order and append each destination.

Then run DFS from "JFK".

During DFS:

1. While the current airport has outgoing flights:
   1. Pop the smallest destination.
   2. DFS from that destination.
2. Append the current airport to route.

Finally reverse route.

Walkthrough

Use:

tickets = [
    ["JFK","SFO"],
    ["JFK","ATL"],
    ["SFO","ATL"],
    ["ATL","JFK"],
    ["ATL","SFO"]
]

Sorted destinations give:

JFK: ATL, SFO
ATL: JFK, SFO
SFO: ATL

We start from JFK.

The smallest destination from JFK is ATL.

So we take:

JFK -> ATL

From ATL, the smallest destination is JFK.

ATL -> JFK

From JFK, the remaining destination is SFO.

JFK -> SFO

From SFO, go to ATL.

SFO -> ATL

From ATL, go to SFO.

ATL -> SFO

Now SFO has no outgoing flights left, so it is appended to the route.

Then recursion unwinds and appends airports after their remaining outgoing flights are exhausted.

The final reversed route is:

["JFK","ATL","JFK","SFO","ATL","SFO"]

Correctness

Each ticket is represented as one directed edge in the graph.

The DFS removes an edge exactly when it uses that ticket:

dfs(graph[airport].pop())

Because removed edges are never inserted again, no ticket is used twice.

The DFS continues from an airport until that airport has no unused outgoing edges. Only then does it append the airport to route. This is the core step of Hierholzer’s algorithm: nodes are added after their outgoing edge chains are fully consumed.

Every edge reachable from "JFK" is eventually removed by the DFS. The problem guarantees a valid itinerary using all tickets, so starting from "JFK" reaches the full Eulerian path.

The route is appended in reverse finishing order. Reversing it gives the forward itinerary.

For lexicographic order, each airport’s outgoing destinations are consumed from smallest to largest. When multiple Eulerian choices are possible, this chooses the lexicographically smallest available edge at the earliest point where the final itinerary can differ. Combined with Hierholzer’s backtracking-by-postorder construction, this produces the smallest valid itinerary.

Therefore, the algorithm returns a valid itinerary that starts at "JFK", uses every ticket exactly once, and is lexicographically smallest.

Complexity

Here, E is the number of tickets.

Each edge is popped exactly once.

Implementation

from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: list[list[str]]) -> list[str]:
        graph = defaultdict(list)

        for src, dst in sorted(tickets, reverse=True):
            graph[src].append(dst)

        route = []

        def dfs(airport: str) -> None:
            while graph[airport]:
                next_airport = graph[airport].pop()
                dfs(next_airport)

            route.append(airport)

        dfs("JFK")

        return route[::-1]

Code Explanation

We build an adjacency list:

graph = defaultdict(list)

Then we sort tickets in reverse order:

for src, dst in sorted(tickets, reverse=True):
    graph[src].append(dst)

This makes the smallest destination appear at the end of each list, so pop() returns the lexicographically smallest destination.

The DFS consumes all outgoing flights from the current airport:

while graph[airport]:
    next_airport = graph[airport].pop()
    dfs(next_airport)

After all outgoing flights are used, we append the airport:

route.append(airport)

This appends airports in reverse itinerary order.

Finally:

return route[::-1]

returns the correct forward route.

Testing

def run_tests():
    s = Solution()

    assert s.findItinerary([
        ["MUC", "LHR"],
        ["JFK", "MUC"],
        ["SFO", "SJC"],
        ["LHR", "SFO"],
    ]) == ["JFK", "MUC", "LHR", "SFO", "SJC"]

    assert s.findItinerary([
        ["JFK", "SFO"],
        ["JFK", "ATL"],
        ["SFO", "ATL"],
        ["ATL", "JFK"],
        ["ATL", "SFO"],
    ]) == ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]

    assert s.findItinerary([
        ["JFK", "A"],
    ]) == ["JFK", "A"]

    assert s.findItinerary([
        ["JFK", "KUL"],
        ["JFK", "NRT"],
        ["NRT", "JFK"],
    ]) == ["JFK", "NRT", "JFK", "KUL"]

    assert s.findItinerary([
        ["JFK", "A"],
        ["JFK", "A"],
        ["A", "JFK"],
    ]) == ["JFK", "A", "JFK", "A"]

    print("all tests passed")

run_tests()

Test meaning: