> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/332-reconstruct-itinerary.md).

# 332 Reconstruct Itinerary

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 belong to a man who departs from`JFK`. Thus, the itinerary must begin with`JFK`.

**Note:**

1. 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"]`.
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

**Example 1:**\
`tickets`=`[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]`\
Return`["JFK", "MUC", "LHR", "SFO", "SJC"]`.

**Example 2:**\
`tickets`=`[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]`\
Return`["JFK","ATL","JFK","SFO","ATL","SFO"]`.\
Another possible reconstruction is`["JFK","SFO","ATL","JFK","ATL","SFO"]`. But it is larger in lexical order.

**The Idea:** This is a eularian path/cycle problem. Our goal is to visit every edge of the graph once, and return to our original position (in our case, which is '`JFK`'). The algorithm that I have used to implement this idea is called *Hierholzer's Algorithm*. More details and discussion here: <https://maksimdan.gitbooks.io/ecs122a-algorithm-design-lecture-notes/content/eularian-cycle.html>

**Complexity:** O(|E|) time and O(|E|) space

```python
from collections import defaultdict


class Solution:
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """

        if not tickets or not tickets[0]:
            return []

        # build representative graph
        g = defaultdict(list)
        for _to, _from in tickets:
            g[_to].append(_from)

        # now sort to create smallest
        # lexicographical itinerary
        for _to, _ in g.items():
            g[_to].sort()

        # maintain an index where the eularian path
        # left off
        left_off = {}
        for _to, _from in tickets:
            left_off[_to] = 0
            left_off[_from] = 0

        itinerary = []
        s = ['JFK']

        # now find the eularian path
        while s:
            top = s[-1]
            g_index = left_off[top]
            g_list = g[top]
            if g_index < len(g_list):
                s.append(g_list[g_index])
                left_off[top] = g_index + 1
            else:
                itinerary.append(top)
                s.pop()

        return list(reversed(itinerary))
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/332-reconstruct-itinerary.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.