invest your 5 minute and learn best solution among all || 2 solutions
Intuition\nMETHOD -> 1\n\nSimple and straight forward intuition is that the node which has indegree 1 and the outdegree 0 that node is our destination node.\n\n
# Intuition\nMETHOD -> 1\n\nSimple and straight forward intuition is that the node which has indegree 1 and the outdegree 0 that node is our destination node.\n\nMETHOD -> 2\n\nSimilar to method 1 we use 2 map for storing indegree and outgree in place of that i use single mapping of string to pair in which i store indegree and outdegree in single map.through this we reduce space complexity.\n\n# Approach\nMETHOD -> 1 \n\nSo for coding method 1 intuition i simoply create two map which maps string to int and store the count of indegree and outdegree of each node and at last we traverse the paths vector and find the node which has indegree equals 1 and the outdegree equals 0 and simply return it. and at last we simply return null string because we know always our answer exists.\n\nMETHOD -> 2\n\nSo for coding method 2 intuition i simply create map of string to pair, where the first value of pair indicates indegree and second value indicate outdegree. and it last we traverse the map and find the node which has indegree 1 and outdegree 0. and simply return it.\nand at last we simply return null string because we know always our answer exists.\n# Complexity\n- Time complexity : O(n)\n\n- Space complexity : O(n)\n\n# Code\n```\nMETHOD -> 1\nclass Solution {\npublic:\n    string destCity(vector<vector<string>>& paths) {\n        unordered_map<string,int> in,out;\n        for(int i=0;i<paths.size();i++){\n            out[paths[i][0]]++;\n            in[paths[i][1]]++;\n        }\n        for(auto val:paths){\n            if(in[val[0]]==1&&out[val[0]]==0)return val[0];\n            else if((in[val[1]]==1&&out[val[1]]==0))return val[1];\n        }\n        return "";\n    }\n};\n\nMETHOD ->2 \nclass Solution {\npublic:\n    string destCity(vector<vector<string>>& path) {\n        unordered_map<string,pair<int,int>> mp;\n        string val1,val2;\n\n        for(int i=0;i<path.size();i++){\n\n            val1=path[i][0];\n            val2=path[i][1];\n\n            if(mp.find(val1)==mp.end())mp[val1]={0,1};\n            else mp[val1]={mp[val1].first,++mp[val1].second};\n\n            if(mp.find(val2)==mp.end())mp[val2]={1,0};\n            else mp[val2]={++mp[val2].first,mp[val2].second};\n\n        }\n        for(auto val:mp){\n            if(val.second.first==1&&val.second.second==0)return val.first;\n        }\n\n        return "";\n    }\n};\n```
['C++']