# LeetCode 332: Reconstruct Itinerary

## Problem Restatement

We are given a list of airline tickets.

Each ticket is a pair:

```text
[from, to]
```

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

We need to reconstruct the itinerary in order.

Rules:

| Rule | Meaning |
|---|---|
| Start airport | The itinerary must start from `"JFK"` |
| Use all tickets | Every ticket must be used exactly once |
| Lexicographic order | If multiple valid itineraries exist, return the smallest one |
| Guarantee | At least one valid itinerary exists |

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

| Item | Meaning |
|---|---|
| Input | `tickets`, a list of `[from, to]` airport pairs |
| Output | A list of airport codes in itinerary order |
| Start | Always `"JFK"` |
| Edge usage | Each ticket is used exactly once |

Function shape:

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

## Examples

Example 1:

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

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

There is only one natural chain:

```text
JFK -> MUC -> LHR -> SFO -> SJC
```

Example 2:

```text
Input:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Output:
["JFK","ATL","JFK","SFO","ATL","SFO"]
```

Another valid itinerary is:

```text
["JFK","SFO","ATL","JFK","ATL","SFO"]
```

But `"ATL"` comes before `"SFO"`, so the required answer starts:

```text
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:

```text
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:

```text
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:

```text
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:

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

Sorted destinations give:

```text
JFK: ATL, SFO
ATL: JFK, SFO
SFO: ATL
```

We start from `JFK`.

The smallest destination from `JFK` is `ATL`.

So we take:

```text
JFK -> ATL
```

From `ATL`, the smallest destination is `JFK`.

```text
ATL -> JFK
```

From `JFK`, the remaining destination is `SFO`.

```text
JFK -> SFO
```

From `SFO`, go to `ATL`.

```text
SFO -> ATL
```

From `ATL`, go to `SFO`.

```text
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:

```text
["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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(E log E)` | Sorting tickets dominates |
| Space | `O(E)` | The graph, recursion stack, and route store ticket data |

Here, `E` is the number of tickets.

Each edge is popped exactly once.

## Implementation

```python
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:

```python
graph = defaultdict(list)
```

Then we sort tickets in reverse order:

```python
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:

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

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

```python
route.append(airport)
```

This appends airports in reverse itinerary order.

Finally:

```python
return route[::-1]
```

returns the correct forward route.

## Testing

```python
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:

| Test | Why |
|---|---|
| Simple chain | Checks direct path reconstruction |
| Multiple choices | Checks lexicographic order |
| One ticket | Minimum meaningful input |
| Greedy trap | Shows why postorder DFS matters |
| Duplicate tickets | Confirms each ticket is used separately |