Reconstruct Itinerary | Leetcode #332


This video explains an important graph programming interview problem which is to reconstruct itinerary.This problem can be solved by using just simple graph traversal technique by using multiset and stack.Map is used to construct the adjacency list because we need random access by string value.Multiset is used to keep the values sorted in ascending order.Stack is used to handle the route exceptions.I have explained the entire problem step by step by using proper examples and intuition for each step.I have dry run the algorithm and have also explained the code walk through at the end of the video.

class Solution {    
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string,multiset<string>> adj;
        vector<string> ans;
        int n=tickets.size();
        //Make graph
        for(int i=0;i<n;++i)
            adj[tickets[i][0]].insert(tickets[i][1]);
        
        stack<string> mystack;
        mystack.push("JFK");    //JFK is our fixed starting point
        while(!mystack.empty())
        {
            string src = mystack.top();
            if(adj[src].size()==0)  //No further travel possible
            {
                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;
    }
};


static int fastio = []() {
    #define endl '\n'
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(0);
    return 0;
}();

Write a comment