332. Reconstruct Itinerary LeetCode Solution

In this guide, you will get 332. Reconstruct Itinerary LeetCode Solution with the best time and space complexity. The solution to Reconstruct Itinerary problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Reconstruct Itinerary solution in C++
  4. Reconstruct Itinerary solution in Java
  5. Reconstruct Itinerary solution in Python
  6. Additional Resources
332. Reconstruct ItineraryLeetCode Solution image

Problem Statement of Reconstruct Itinerary

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:

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.

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

Complexity Analysis

  • Time Complexity: O(|E|\log |E|)
  • Space Complexity: O(|E|)
See also  46. Permutations LeetCode Solution

332. Reconstruct Itinerary LeetCode Solution in C++

class Solution {
 public:
  vector<string> findItinerary(vector<vector<string>>& tickets) {
    vector<string> ans;
    unordered_map<string, multiset<string>> graph;

    for (const vector<string>& ticket : tickets)
      graph[ticket[0]].insert(ticket[1]);

    dfs(graph, "JFK", ans);
    ranges::reverse(ans);
    return ans;
  }

 private:
  void dfs(unordered_map<string, multiset<string>>& graph, const string& u,
           vector<string>& ans) {
    while (graph.contains(u) && !graph[u].empty()) {
      const string v = *graph[u].begin();
      graph[u].erase(graph[u].begin());
      dfs(graph, v, ans);
    }
    ans.push_back(u);
  }
};
/* code provided by PROGIEZ */

332. Reconstruct Itinerary LeetCode Solution in Java

class Solution {
  public List<String> findItinerary(List<List<String>> tickets) {
    LinkedList<String> ans = new LinkedList<>();
    Map<String, Queue<String>> graph = new HashMap<>();

    for (final List<String> ticket : tickets) {
      graph.putIfAbsent(ticket.get(0), new PriorityQueue<>());
      graph.get(ticket.get(0)).offer(ticket.get(1));
    }

    dfs(graph, "JFK", ans);
    return ans;
  }

  private void dfs(Map<String, Queue<String>> graph, final String u, LinkedList<String> ans) {
    final Queue<String> arrivals = graph.get(u);
    while (arrivals != null && !arrivals.isEmpty())
      dfs(graph, arrivals.poll(), ans);
    ans.addFirst(u);
  }
}
// code provided by PROGIEZ

332. Reconstruct Itinerary LeetCode Solution in Python

class Solution:
  def findItinerary(self, tickets: list[list[str]]) -> list[str]:
    ans = []
    graph = collections.defaultdict(list)

    for a, b in reversed(sorted(tickets)):
      graph[a].append(b)

    def dfs(u: str) -> None:
      while u in graph and graph[u]:
        dfs(graph[u].pop())
      ans.append(u)

    dfs('JFK')
    return ans[::-1]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.