Leetcode: Reconstruct Itinerary.

 

This question is asked at Uber, Amazon, Microsoft, Twilio, Bloomberg, Google, Expedia, and many more. 

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 and return it. The itinerary starts at JFK. 

Here's an example: 

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

Output: ["JFK","MUC","LHR","SFO","SJC"]

There are two possible solutions to this problem. The first one is called backtracking, used to enumerate all possible solutions for a problem in a trial fail and fallback strategy. We want to follow a heuristic to solve a problem. It would lead to a reasonable approximation in exchange for less computing time. 

We would pick each destination greedily in order. 

1. Build a graph data structure for the input, adopting a hash map data structure.

2. Order the destination list/graph in lexical order

3. Kick off the Backtracking traversal of the graph

class Solution {

  // origin -> list of destinations

  HashMap<String, List<String>> flightMap = new HashMap<>();

  HashMap<String, boolean[]> visitBitmap = new HashMap<>();

  int flights = 0;

  List<String> result = null;

  public List<String> findItinerary(List<List<String>> tickets) {

    //for all the tickets, add the destinationlist to the index of the location origin flightmap

    for (List<String> ticket : tickets) {

      String origin = ticket.get(0);

      String dest = ticket.get(1);

      if (this.flightMap.containsKey(origin)) {

        List<String> destList = this.flightMap.get(origin);

        destList.add(dest);

      } else {

        List<String> destList = new LinkedList<String>();

        destList.add(dest);

        this.flightMap.put(origin, destList);

      }

    }

    // Step 2). order the destinations and init the visit bitmap

    //look at the flight map entry and put a visited list inside of the bitmap of visited locations. 

    for (Map.Entry<String, List<String>> entry : this.flightMap.entrySet()) {

      Collections.sort(entry.getValue());

      this.visitBitmap.put(entry.getKey(), new boolean[entry.getValue().size()]);

    }

    this.flights = tickets.size();

    LinkedList<String> route = new LinkedList<String>();

    route.add("JFK");

    // Step 3). backtracking

    this.backtracking("JFK", route);

    return this.result;

  }

  protected boolean backtracking(String origin, LinkedList<String> route) {

    if (route.size() == this.flights + 1) {

      this.result = (List<String>) route.clone();

      return true;

    }

    //see if there is the origin inside of the flight map.

    if (!this.flightMap.containsKey(origin))

      return false;

    int i = 0;

    boolean[] bitmap = this.visitBitmap.get(origin);

    

    for (String dest : this.flightMap.get(origin)) {

      if (!bitmap[i]) {

        //backtracking step where we are supposed to get the bitmap and add destination

        bitmap[i] = true;

        route.add(dest);

        boolean ret = this.backtracking(dest, route);

        route.pollLast();

        //return the last element of the route and make the bitmap value false. 

        bitmap[i] = false;

        if (ret)

          return true;

      }

      ++i;

    }

    return false;

  }

}

Now the next approach to this question will be explained by the youtube TECHDOES. This Video provides a good reference. You need to traverse in lexical order. 

From the ticket array, I have formed an adjacency list, and then get a graphical representation of the list. 

The observation means that the tickets are only one-way, therefore, we would only draw directed edges from A to B.

The second observation is to return the root with the smallest lexical order which means the least/earliest we can travel inside of the dictionary. The third observations that all of the tickets form a valid root where we are able to get to a path, so it's going to be a directed graph with all of its components reachable.  You can try to traverse through the adjacency list. 

We can use an edge only once, we can't go from A to b then go from A to 2. If you have a cycle, all of the edges will only be covered once.

Cover all edges exactly once, choose lexically ordered option for travel, start at JFK, and return your route as the answer.  How do you maintain lexicographical order? You sort through all of the lists! 

The choice of Data structure for this is VERY important! You can use a map, vector, and multiset. 

The multiset keeps vales arranged and a map for O(1) search time for the given key. A stack might work for this. A stack may work for this, going form J to K, adding all elements from K and seeing elements from the stack. So map, multiset, and stack. 

1. cover each and every edge

2. cover the edges in lexical order. 

You can also use data structures. Let's solve an example

Push the first element into stack and go to the element inside of the adjacency list, and keep pushing the next element in the adjacency lists until no elements are left inside of the array. Pop the elements, and finally store the elements inside a backwards function. Always make sure the values in the adjacency lists are ordered lexically smaller. 

Here's the final code: 

class Solution {

    public: 

        vector<string> findItenerar(vector<vector<string> & tickets) {

            unordered_map<string, multiset<string>> adj;

            vector<string> ans;

            int n = tickets.size();

            for(int i = 0; i < n; ++i) {

                adj[tickets[i][0]].insert(tickets[i][1]);

            }

            stack<string> mystack;

            mystack.push("JFK"); 

            while(!mystack.empty()) {

                string src = mystack.top();

                if(adj[src].size() == 0) {

                    ans.push_back(src);

                    mystack.pop();

                } else {

                    auto dst = adj[src].begin();

                    mystack.push(*dst);

                    adj[src].erase(dst);

              }

            }

            reverse(ans.begin(), ans.end());

            return ans; 

        }

};