Easy Soluyion beats 86% userss C++
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is to find the destination city, which is the city without any outgoing pat
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is to find the destination city, which is the city without any outgoing path. We can model the relationships between cities as a directed graph, where each directed edge represents a direct path from one city to another.\n\nThe intuition is to use a data structure to keep track of the outgoing paths for each city. We can then start from any city and follow the outgoing paths until we reach a city with no further outgoing path. This city will be the destination city.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBuild Outgoing Map:\n\nCreate an unordered map (outgoing) to store the outgoing paths for each city.\nIterate through the input paths vector and populate the outgoing map.\nFind Destination City:\n\nStart with any city (let\'s choose the first city from the input paths) and follow the outgoing paths until we reach a city with no further outgoing path.\nThe city without any outgoing path is the destination city.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nBuilding the outgoing map takes O(N) time, where N is the number of paths.\nFinding the destination city involves traversing the outgoing paths, taking O(N) time in the worst case.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(N) to store the outgoing map, where N is the number of paths.\nAdditional space complexity is O(1) for other variables.\nThus, the overall space complexity is O(N).\n\n# Code\n```\nclass Solution {\npublic:\n    string destCity(vector<vector<string>>& paths) {\n        unordered_map<string, string> outgoing;\n\n        for (const auto& path : paths) {\n            outgoing[path[0]] = path[1];\n        }\n\n        string startCity = paths[0][0];\n        \n        while (outgoing.find(startCity) != outgoing.end()) {\n            startCity = outgoing[startCity];\n        }\n\n        return startCity;\n\n\n    }\n};\n```
['C++']