# Reconstruct Itinerary
**Difficulty:** HARD
[External](https://leetcode.com/problems/reconstruct-itinerary)
Canonical: https://scaleengineer.com/dsa/problems/reconstruct-itinerary
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Eulerian Circuit](https://scaleengineer.com/algorithms/eulerian-circuit)
**Data structures:** Graph
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Yandex](https://scaleengineer.com/companies/yandex), [eBay](https://scaleengineer.com/companies/ebay), [Netflix](https://scaleengineer.com/companies/netflix), [Snap](https://scaleengineer.com/companies/snap), [Booking.com](https://scaleengineer.com/companies/booking.com), [Pinterest](https://scaleengineer.com/companies/pinterest), [Twilio](https://scaleengineer.com/companies/twilio)
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/reconstruct-itinerary/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/reconstruct-itinerary/image1.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`

# Approaches
## Brute-force Backtracking
This approach employs a standard backtracking algorithm using Depth-First Search (DFS). The idea is to explore all possible valid itineraries starting from "JFK". We model the airports and flights as a directed graph. To ensure the final itinerary is the lexicographically smallest, we always explore flights to destinations in alphabetical order. The first complete itinerary found will be the correct answer. We keep track of used tickets to ensure each is used exactly once. If a path leads to a dead end (i.e., we get stuck before using all tickets), we backtrack and try a different path.
**Time:** O(d^E) in the worst case, where d is the maximum out-degree of an airport and E is the number of tickets. The algorithm might explore a number of paths that is exponential in the number of tickets, making it too slow for the given constraints. · **Space:** O(V + E), where V is the number of airports and E is the number of tickets. This space is used to store the graph, the visited map, and the recursion stack.
**Pros:** Conceptually straightforward and easy to understand for those familiar with DFS and backtracking.
**Cons:** Highly inefficient and likely to result in a 'Time Limit Exceeded' error for larger inputs.; The search can go very deep down a wrong path before backtracking, especially if the lexicographically smallest choices lead to a dead end where not all tickets can be used.
### Explanation
The implementation begins by constructing a graph from the list of tickets. An adjacency list, represented by a `HashMap`, maps each departure airport to a list of its destinations. Crucially, each list of destinations is sorted lexicographically to guide the DFS towards the smallest lexical itinerary.

To handle duplicate flights (e.g., two tickets from "JFK" to "SFO"), we can't simply mark a destination as visited. Instead, we need to track the usage of each specific ticket. A `Map<String, boolean[]>` serves this purpose, where for each departure airport, a boolean array tracks the used status of each of its outgoing flights, corresponding to the sorted destination list.

The core of the solution is a recursive `dfs` function. It attempts to build the itinerary step by step. Starting from "JFK", it tries to fly to the first available destination in the sorted list. It marks that ticket as used and recursively calls itself for the arrival airport. If this path eventually uses all tickets (i.e., the path length becomes `num_tickets + 1`), a solution is found. If the recursive call fails to find a complete path, it backtracks by unmarking the ticket and trying the next available destination.

```java
class Solution {
    private Map<String, List<String>> adj = new HashMap<>();
    private Map<String, boolean[]> visited;
    private int numTickets = 0;
    private List<String> result = null;

    public List<String> findItinerary(List<List<String>> tickets) {
        this.numTickets = tickets.size();
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            this.adj.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        }

        this.visited = new HashMap<>();
        for (Map.Entry<String, List<String>> entry : this.adj.entrySet()) {
            Collections.sort(entry.getValue());
            this.visited.put(entry.getKey(), new boolean[entry.getValue().size()]);
        }

        LinkedList<String> path = new LinkedList<>();
        path.add("JFK");
        dfs("JFK", path);
        return this.result;
    }

    private boolean dfs(String from, LinkedList<String> path) {
        if (path.size() == this.numTickets + 1) {
            this.result = new ArrayList<>(path);
            return true;
        }

        if (!this.adj.containsKey(from)) {
            return false;
        }

        List<String> destinations = this.adj.get(from);
        boolean[] used = this.visited.get(from);

        for (int i = 0; i < destinations.size(); i++) {
            if (!used[i]) {
                used[i] = true;
                path.add(destinations.get(i));
                if (dfs(destinations.get(i), path)) {
                    return true;
                }
                path.removeLast();
                used[i] = false;
            }
        }
        return false;
    }
}
```
### Algorithm
*   Build a graph where airports are nodes and tickets are directed edges. An adjacency list, like `Map<String, List<String>>`, is a good representation.
*   For each airport, sort its list of destinations lexicographically. This ensures that when exploring from an airport, we try the lexicographically smallest destination first.
*   To handle duplicate tickets, we need a way to track which specific ticket has been used. A `Map<String, boolean[]>` can be used, where for each `from` airport, we have a boolean array corresponding to its sorted destination list. `visited.get("JFK")[0]` would track the first flight from JFK in its sorted list of destinations.
*   Define a recursive DFS function, say `dfs(from, path)`.
*   The base case for the recursion is when the path length equals the number of tickets plus one. At this point, a valid itinerary has been found. Since we explore in lexicographical order, the first one we find is the answer, and we can stop the search.
*   In the recursive step, for the current airport, iterate through its destinations. For each unused ticket to a destination, mark it as used and make a recursive call for the destination airport.
*   If a recursive call returns `true` (solution found), propagate this up the call stack.
*   If the recursive call leads to a dead end (returns `false`), we must backtrack. This involves unmarking the ticket as used so it can be part of another path.

## Hierholzer's Algorithm (Optimal)
This problem is equivalent to finding an Eulerian path in a directed graph, for which Hierholzer's algorithm is a perfect fit. This approach is both elegant and efficient. We perform a single pass DFS-like traversal through the graph. The key idea is to build the itinerary backward. When we get stuck at an airport (i.e., there are no more outgoing flights to take), we add it to the head of our result list. To satisfy the lexicographical requirement, we use a `PriorityQueue` to store the destinations for each airport, ensuring we always visit the alphabetically smallest destination first.
**Time:** O(E log E), where E is the number of tickets. Building the graph takes O(E log d_max) where d_max is the max out-degree, bounded by O(E log E). The traversal visits each edge once, and each visit involves a `poll` operation from a priority queue, taking O(log d) time. The total time is dominated by these operations. · **Space:** O(V + E), where V is the number of unique airports and E is the number of tickets. This space is for the adjacency list, the recursion stack, and the result list.
**Pros:** Very efficient and is the standard algorithm for finding Eulerian paths.; Correctly and elegantly finds the lexicographically smallest itinerary without expensive backtracking.; Guaranteed to find a solution since the problem statement ensures one exists.
**Cons:** The post-order traversal logic for building the path backward can be less intuitive than a direct path-building approach.
### Explanation
The algorithm starts by building a graph representation of the flights. A `HashMap` where keys are departure airports and values are `PriorityQueue`s of destination airports is ideal. The `PriorityQueue` naturally maintains destinations in lexicographical order, so when we request the next flight, we always get the one to the alphabetically smallest airport.

The core of the algorithm is a recursive function, let's call it `dfs`, that performs a post-order traversal of the graph. We start the traversal from "JFK". For a given airport, the `dfs` function iterates through all its outgoing flights. It does this by polling from the airport's priority queue, which removes the flight and ensures we don't use it again. For each flight, it makes a recursive call to `dfs` with the destination airport.

Once the `dfs` function has exhausted all outgoing flights from an airport (the priority queue for that airport becomes empty), it adds that airport to the *front* of the result list. This is the crucial step of Hierholzer's algorithm. The first airport to be added to the list is the final destination of the itinerary. The starting airport, "JFK", will be the last to have its `dfs` call complete, so it will be added last to the front of the list, correctly placing it at the beginning of the itinerary.

```java
class Solution {
    // Adjacency list using a PriorityQueue to handle lexical order
    private Map<String, PriorityQueue<String>> adj = new HashMap<>();
    // The final itinerary, built backwards
    private LinkedList<String> itinerary = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        // Build the graph
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            adj.computeIfAbsent(from, k -> new PriorityQueue<>()).add(to);
        }
        
        // Start the DFS-like traversal from "JFK"
        dfs("JFK");
        
        return itinerary;
    }

    private void dfs(String airport) {
        // Visit all the destinations from the current airport
        PriorityQueue<String> destinations = adj.get(airport);
        while (destinations != null && !destinations.isEmpty()) {
            // Poll the next destination to visit it and remove the edge
            String nextAirport = destinations.poll();
            dfs(nextAirport);
        }
        // Add the airport to the front of the list after visiting all its destinations
        itinerary.addFirst(airport);
    }
}
```
### Algorithm
*   Represent the flights as a directed graph. Use a `Map<String, PriorityQueue<String>>` for the adjacency list. The `PriorityQueue` will ensure that we can always access and remove the lexicographically smallest destination efficiently.
*   Populate the graph from the input `tickets`. For each ticket `[from, to]`, add `to` to the `PriorityQueue` of `from`.
*   Initialize an empty `LinkedList<String>` to store the final itinerary.
*   Implement a recursive DFS function, say `dfs(airport)`.
*   Inside `dfs(airport)`, get the `PriorityQueue` of destinations for the current `airport`. While the queue is not empty, `poll()` the next destination and make a recursive call: `dfs(nextDestination)`.
*   After the `while` loop finishes (meaning all outgoing flights from `airport` have been visited), add the `airport` to the *front* of the itinerary list.
*   Start the process by calling `dfs("JFK")`.
*   The final `itinerary` list will hold the reconstructed path in the correct order.

# Solutions
### Java

```java
class Solution {
  void dfs(Map<String, Queue<String>> adjLists, List<String> ans, String curr) {
    Queue<String> neighbors = adjLists.get(curr);
    if (neighbors == null) {
      ans.add(curr);
      return;
    }
    while (!neighbors.isEmpty()) {
      String neighbor = neighbors.poll();
      dfs(adjLists, ans, neighbor);
    }
    ans.add(curr);
    return;
  }
public
  List<String> findItinerary(List<List<String>> tickets) {
    Map<String, Queue<String>> adjLists = new HashMap<>();
    for (List<String> ticket : tickets) {
      String from = ticket.get(0);
      String to = ticket.get(1);
      if (!adjLists.containsKey(from)) {
        adjLists.put(from, new PriorityQueue<>());
      }
      adjLists.get(from).add(to);
    }
    List<String> ans = new ArrayList<>();
    dfs(adjLists, ans, "JFK");
    Collections.reverse(ans);
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> findItinerary(vector<vector<string>> &tickets) {
    unordered_map<string,
                  priority_queue<string, vector<string>, greater<string>>>
        g;
    vector<string> ret;
```

### Python

```python
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) itinerary = [] def dfs(airport): while graph[airport]: dfs(graph[airport]. pop()) itinerary . append(airport) dfs("JFK") return itinerary[:: - 1]

```