> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Reconstruct Itinerary Python Solution

> Tested Python solution for LeetCode 332 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 332, Hard. Topics: Array, String, Depth-First Search, Graph Theory, Sorting, Heap (Priority Queue), Eulerian Circuit. [View on LeetCode](https://leetcode.com/problems/reconstruct-itinerary/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 332   # by problem number
lcpy gen -s reconstruct_itinerary   # by problem name
```

## Problem

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

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

* For example, the itinerary `["JFK", "LGA"]` has a smaller lexical order than `["JFK", "LGB"]`.

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/03/14/itinerary1-graph.jpg)

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

![Example 2](https://assets.leetcode.com/uploads/2021/03/14/itinerary2-graph.jpg)

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

**Explanation:** Another possible reconstruction is \["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

### Constraints

* 1 \<= tickets.length \<= 300
* tickets\[i].length == 2
* fromi.length == 3
* toi.length == 3
* fromi and toi consist of uppercase English letters.
* fromi != toi

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/reconstruct_itinerary/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/reconstruct_itinerary/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(E log E)
    # Space: O(E)
    def find_itinerary(self, tickets: list[list[str]]) -> list[str]:
        graph: dict[str, list[str]] = {}
        for src, dst in tickets:
            graph.setdefault(src, []).append(dst)
        for src in graph:
            graph[src].sort(reverse=True)

        itinerary: list[str] = []

        def dfs(airport: str) -> None:
            destinations = graph.get(airport)
            while destinations:
                dfs(destinations.pop())
            itinerary.append(airport)

        dfs("JFK")
        itinerary.reverse()
        return itinerary
```

## Complexity

| Time       | Space |
| ---------- | ----- |
| O(E log E) | O(E)  |

## Tags

[NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).