Last updated on January 14th, 2025 at 06:25 am

Here, we see a Reconstruct Itinerary LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth-First Search, Graph

Companies

Google

Level of Question

Hard

Reconstruct Itinerary LeetCode Solution

1. Problem Statement

You are given a list of airline tickets where tickets[i] = [from_i, to_i] 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:

Input: tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
Output: [“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”]
Explanation: Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”] but it is larger in lexical order.

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Hierholzer’s Algorithm for Eulerian Path”. This algorithm is used to find an Eulerian path or circuit in a graph, which is a path that visits every edge exactly once. The problem involves reconstructing an itinerary from a list of tickets, which can be modeled as finding an Eulerian path in a directed graph.

3. Code Implementation in Different Languages

3.1 Reconstruct Itinerary C++

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, vector<string>> graph;
        for (auto& ticket : tickets) {
            graph[ticket[0]].push_back(ticket[1]);
        }
        for (auto& [_, destinations] : graph) {
            sort(destinations.rbegin(), destinations.rend());
        }
        vector<string> itinerary;
        function<void(const string&)> dfs = [&](const string& airport) {
            while (!graph[airport].empty()) {
                string next = graph[airport].back();
                graph[airport].pop_back();
                dfs(next);
            }
            itinerary.push_back(airport);
        };
        dfs("JFK");
        reverse(itinerary.begin(), itinerary.end());
        return itinerary;        
    }
};

3.2 Reconstruct Itinerary Java

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (List<String> ticket : tickets) {
            graph.putIfAbsent(ticket.get(0), new PriorityQueue<>());
            graph.get(ticket.get(0)).add(ticket.get(1));
        }
        LinkedList<String> itinerary = new LinkedList<>();
        dfs("JFK", graph, itinerary);
        return itinerary;
    }
    private void dfs(String airport, Map<String, PriorityQueue<String>> graph, LinkedList<String> itinerary) {
        PriorityQueue<String> nextAirports = graph.get(airport);
        while (nextAirports != null && !nextAirports.isEmpty()) {
            dfs(nextAirports.poll(), graph, itinerary);
        }
        itinerary.addFirst(airport);
    }
}

3.3 Reconstruct Itinerary JavaScript

var findItinerary = function(tickets) {
    const graph = {};
    for (const [src, dst] of tickets) {
        if (!graph[src]) graph[src] = [];
        graph[src].push(dst);
    }
    for (const key in graph) {
        graph[key].sort().reverse();
    }
    const itinerary = [];
    function dfs(airport) {
        while (graph[airport] && graph[airport].length > 0) {
            dfs(graph[airport].pop());
        }
        itinerary.push(airport);
    }
    dfs("JFK");
    return itinerary.reverse();
};

3.4 Reconstruct Itinerary Python

class Solution(object):
    def findItinerary(self, tickets):
        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]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(E log E)	O(V + E)
Java	O(E log E)	O(V + E)
JavaScript	O(E log E)	O(V + E)
Python	O(E log E)	O(V + E)

where V is the number of airports (vertices) and E is the number of tickets (edges).

The algorithm ensures lexicographical order by sorting the destinations in reverse order and using a stack-like traversal.
The reverse operation at the end ensures the itinerary is in the correct order.
The use of a recursive DFS is common in problems involving graph traversal.