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

• 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;
}
};
``````

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

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