C++ non-recursive O(N)-time O(N)-space solution with detail explanations


  • 19

    The idea of this algorithm, which was originally found in fangyang's thread https://leetcode.com/discuss/84706/share-solution-java-greedy-stack-15ms-with-explanation, consists of two steps:

    • Step 1: Store the flight in a hash map. (say m in the code below. This map enables us to find all possible destinations from a place in amortized constant time.)

    • Step 2: Use a greedy and trace-back approach to find the optimal itinerary. Specifically, we use greedy method to find a lexicographically-smallest path until we can not move any further (the path can be stored in a vector, say march in the code below). Each time we reach such an exhaustive state, we find a place which is exactly the end of the itinerary. (The reason is, the path march is an optimal itinerary expect that some loops are omitted. The optimal itinerary can be obtained by inserting some loops into this path, which does not change the last vertex of the path.) Therefore, we can record the last vertex in another place (say results in the code below). So and so forth, the vector results stores the optimal itinerary reversely, since we always place the optimal last vertex at the end of this vector. Reversing the vertex results leads to the correct answer.


    Example:
    This example is originally shown in StefanPochmann's thread https://leetcode.com/discuss/84659/short-ruby-python-java-c


    [ Source of this picture: http://www.stefan-pochmann.info/misc/reconstruct-itinerary.png ]

    In Step 2, we first march greedily, and get the vector march as:

    march: JFK -> A -> C -> D -> A      (the red path)
    

    However, the optimal itinerary, is

    JFK -> A -> C -> D( -> B -> C -> JFK -> D) -> A
    

    where the loop (D -> B -> C -> JFK -> D) shall be inserted in the vector march. However, we have already found the last vertex A, Therefore, we can record this result. So march and results become

    march: JFK -> A -> C -> D
    results: A
    

    Then we march greedily again, results in

    march: JFK -> A -> C -> D -> B -> C -> JFK -> D
    results: A
    

    Now all edges are used. Before the final reversion, march and results become

    march: (empty)
    results: A <- D <- JFK <- C <- B <- D <- C <- A <- JFK
    

    Overall Complexities:

    Let N be the number of tickets. Let D be the largest outgoing degree of a vertex.

    • Time: O(N log D)
      Step 1: O(N log D)
      Step 2: O(N). Each vertex needs to be put into march once and be moved from march to results. At the very end, results is reversed.
    • Space: O(N)
      The map m needs to store all vertices.

    Code (40 ms):

    class Solution {
    public:
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            
            // Step 1: Store directed edges in a hash map
            unordered_map<string, multiset<string>> m;
            for (const pair<string, string> & ticket : tickets) {
                m[ticket.first].insert(ticket.second);
            }
            
            // Step 2: March greedily and traceback
            vector<string> march = { "JFK" }; // the storage for greedy searching
            vector<string> results; // store the final results reversely
            while (march.empty() == false) {
                string & from = march.back();
                if ((m.find(from) != m.end()) && (m[from].empty() == false)) { // march further
                    multiset<string> & to = m[from];
                    march.push_back(*(to.begin()));
                    to.erase(to.begin());
                } else { // can not march further, trace back
                    results.push_back(march.back()); // archive the last place
                    march.pop_back();
                }
            }
            reverse(results.begin(), results.end()); // reverse the entries back
            return results;
        }
    };
    

  • 0
    R

    I think it's the same as using stack. essentially you're using vector as a stack.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.