Leetcode 332. Reconstruct Itinerary

Problem Explanation

This problem is about itinerary reconstruction. We are given a list of tickets, where each ticket is represented as pairs of departure and arrival airports. We need to calculate the itinerary by following these tickets starting from "JFK" airport.

The problem has the following constraints:

1. The itinerary must start from "JFK" as the problem states that "All of the tickets belong to a man who departs from JFK."
2. If there are multiple valid itineraries, we need to return the itinerary that has the smallest lexical order. So, if we have ["JFK", "LGA"] and ["JFK", "LGB"], we have to select the first one because "LGA" has a smaller lexical order than "LGB".
3. All airports are represented by three capital letters (IATA code) and a valid itinerary is guaranteed.

Approach to the Solution

We can treat this problem as a graph problem. A graph consists of a set of nodes (airports in this case) and edges (tickets). We are going to traverse the graph in Depth-first-search (DFS) order starting from "JFK" node. A multiset is used to hold each destination reachable from each airport, sorted by lexical order. Multisets in C++ automatically keep the elements in sorted order (smallest to largest), which will make sure we choose the smallest lexical order route when multiple routes are present.

We perform DFS traversal on the graph starting from "JFK" airport and whenever we reach a node with no outgoing edges (no possible destinations), we add that node to our answer list.

Here's how the algorithm works with an example:

Consider the following tickets [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]].

• Construct a graph. The adjacency list representation of the graph is:

  1
  2
  3"JFK" --> ["ATL", "SFO"]
  4"ATL" --> ["JFK", "SFO"]
  5"SFO" --> ["ATL"]

• We start DFS traversal from "JFK".

• Among the available options "ATL" and "SFO", "ATL" is lexicographically smaller. So go to "ATL".

• From "ATL" we can go to "JFK" and "SFO". Since "JFK" is lexicographically smaller, go to "JFK".

• Do the same process till all tickets are exhausted.

• Finally we end up with the journey "JFK" → "ATL" → "JFK" → "SFO" → "ATL" → "SFO".

Solution (C++)

1
2cpp
3class Solution {
4 public:
5  vector<string> findItinerary(vector<vector<string>>& tickets) {
6    vector<string> ans; // to hold the final itinerary.
7    unordered_map<string, multiset<string>> graph; 
8
9    // construct the graph with the given tickets.
10    for (const vector<string>& ticket : tickets)
11      graph[ticket[0]].insert(ticket[1]);
12
13    dfs(graph, "JFK", ans);
14    reverse(begin(ans), end(ans)); // reverse the answer to get the correct order.
15    return ans;
16  }
17
18 private:
19  void dfs(unordered_map<string, multiset<string>>& graph, const string& u, vector<string>& ans) {
20    // continue to traverse while the current airport has destinations.
21    while (graph.count(u) && !graph[u].empty()) {
22      const string v = *begin(graph[u]); // get the first destination.
23      graph[u].erase(begin(graph[u])); // remove the ticket from graph.
24      dfs(graph, v, ans); // continue with the destination.
25    }
26    ans.push_back(u); // no more destinations left, add the airport to the itinerary.
27  }
28};

The unordered_map is used to quickly access the list of possible destinations for each airport, and multiset is used to keep the destinations sorted in lexical order. The dfs function visits all nodes reachable from the given node in depth-first order, removing visited edges along the way. When it has finished visiting all reachable nodes, it adds the current node to the ans vector. Because all nodes reachable from the given node must be visit before the current node itself, the ans vector is finally reversed.## Solution (Python)

1
2python
3from collections import defaultdict
4
5class Solution:
6    def findItinerary(self, tickets):
7        def visit(airport):
8            while targets[airport]:
9                visit(targets[airport].pop())
10            route.append(airport)
11
12        targets = defaultdict(list)
13        for a, b in sorted(tickets)[::-1]:
14            targets[a] += b,
15        route = []
16        visit('JFK')
17        return route[::-1]

In Python, we can achieve the same using defaultdict from the collections module. Here the function visit traverses the graph in DFS order, starting from 'JFK'. While traversing we pop each visited node and append it to our output list route. In our implementation, we sort the tickets in reverse order before inserting into our dictionary targets. The reason to do so is Python’s list pop() operation removes the last element in the list, this is precisely what allows us to simply use a dictionary and lists to perform the itinerary calculations as opposed to a multiset and priority queue.

Solution (JavaScript)

1
2js
3/**
4 * @param {string[][]} tickets
5 * @return {string[]}
6 */
7var findItinerary = function(tickets) {
8    const map = {};
9    const result = [];
10    tickets.sort();
11    for(let i=0;i<tickets.length;i++){
12        let [from, to] = tickets[i];
13        if(map[from] === undefined) map[from] = [];
14        map[from].push(to);
15    }
16    const stack = ['JFK'];
17    while(stack.length){
18        while(map[stack[stack.length-1]] && map[stack[stack.length-1]].length){
19            let airport = map[stack[stack.length-1]].pop();
20            stack.push(airport);
21        }
22        result.unshift(stack.pop());
23    }    
24    return result;
25};

In JavaScript, we create an adjacency list using JavaScript object (acting as a HashMap) to represent the graph. Then we sort the tickets array so that we visit all airports in lexicographical order. 'stack' is our DFS stack and 'result' is an array which will store our final itinerary. For each airport, we keep popping from the 'stack' and adding to 'result' if there are no more outgoing edges from it, otherwise we keep DFSing.

Solution (Java)

1
2java
3class Solution {
4    public List<String> findItinerary(List<List<String>> tickets) {
5        LinkedList<String> result = new LinkedList<>();
6        Map<String, PriorityQueue<String>> graph = new HashMap<>();
7        for(List<String> ticket : tickets) {
8            graph.putIfAbsent(ticket.get(0), new PriorityQueue<>());
9            graph.get(ticket.get(0)).offer(ticket.get(1));
10        }
11        dfs(graph, "JFK", result);
12        return result;
13    }
14    void dfs(Map<String, PriorityQueue<String>> graph, String airport, LinkedList<String> result) {
15        PriorityQueue<String> dests = graph.get(airport);
16        while(dests != null && !dests.isEmpty()) {
17            dfs(graph, dests.poll(), result);
18        }
19        result.addFirst(airport);
20    }
21}

In Java, we solve the problem by using Hashmap to store the graph and PriorityQueue to guarantee next stop is chosen by the lexical order. We perform DFS from 'JFK', and keep moving to the destination by extracting the top of PriorityQueue until there are no tickets (outgoing edges) left. Then we add this airport into the output list as the first element, which will automatically reverse the itinerary and fulfill the requirement to add an airport when we are done with its tickets.