"🧠 Intuitive Solution in C++ | ⏳ 0ms Runtime (Top 5%) | ✅ Beginner-Friendly Explanation"
Intuition\n\nI thought this as topological sort problem but since there is only one node with no outgoing edge therefore the solution becomes much much easier t
# Intuition\n<h2>\nI thought this as topological sort problem but since there is only one node with no outgoing edge therefore the solution becomes much much easier to think.<br><br>\nBut first Step is to think this as topological sort problem.\n<br><br>\n\nEdit : Topological Sort got nothing to do with the provided solution so don\'t be scared of such fancy term.\n\n<br>\n<br>\n\nThe code is designed to find the destination city in a list of paths, where each path is represented by a pair of cities [u, v], indicating a directed edge from city u to city v. The goal is to identify the city that is the ultimate destination and does not have any outgoing paths.\n\n\n\n# Approach\n**Approach to Find the Destination City:**\n\n1. **Initialize Outgoing and Incoming Sets:**\n   - Create two empty sets, `outgoing` and `incoming`, to store the source and destination cities.\n\n2. **Populate Outgoing and Incoming Sets:**\n   - Iterate through the given `paths` list, and for each pair [u, v]:\n     - Add `u` to the `outgoing` set.\n     - Add `v` to the `incoming` set.\n\n3. **Find the Destination City:**\n   - Iterate through the `incoming` set.\n   - For each destination city `u`:\n     - Check if `u` is not present in the `outgoing` set.\n     - If found, return `u` as the destination city.\n\n4. **Handle Edge Cases:**\n   - If the input is well-formed, there should be exactly one destination city without any outgoing paths.\n   - If no such city is found, it implies an issue with the input, and an appropriate response (e.g., an error message or default value) may be provided.(Though it is given in question that unique answer always exists but for interview pov keep this point in mind:) )\n\n**Note:**\n- The use of sets ensures constant-time membership checks, making the solution efficient.Otherwise looking-up in python list or c++ vector take O(n) time complexity. btw you can use them.\n\n**Complexity Analysis:**\n- Time Complexity: O(N), where N is the number of paths.\n- Space Complexity: O(N), as we use two sets to store the outgoing and incoming cities.\n\n\n# Code\n\n```Python []\nclass Solution:\n    def destCity(self, paths: List[List[str]]) -> str:\n        outgoing = set()\n        incoming = set()\n        for u,v in paths:\n            outgoing.add(u)\n            incoming.add(v)\n\n        for u in incoming:\n            if u not in outgoing:\n                return u\n        \n```\n\n```C++ []\nclass Solution {\npublic:\n    string destCity(vector<vector<string>>& paths) {\n        unordered_set<string> outgoing;\n        unordered_set<string> incoming;\n\n        for (const auto& path : paths) {\n            outgoing.insert(path[0]);\n            incoming.insert(path[1]);\n        }\n\n        for (const auto& city : incoming) {\n            if (outgoing.find(city) == outgoing.end()) {\n                return city;\n            }\n        }\n    }\n};\n```
['Hash Table', 'String', 'Graph', 'C++', 'Python3']