✅Beats 100% - Explained with [ Video ] - HashSet - C++/Java/Python/JS  - Visualized
\n\n\n# YouTube Video Explanation:\n\nhttps://youtu.be/vaXdR0lDW6A\n **If you want a video for this question please write in the comments** \n\n\uD83D\uDD25 Ple
![Screenshot 2023-12-15 074825.png](https://assets.leetcode.com/users/images/4952f405-362e-45da-b0e0-5ca8f8d82d0a_1702607487.4331408.png)\n\n\n# YouTube Video Explanation:\n\n[https://youtu.be/vaXdR0lDW6A](https://youtu.be/vaXdR0lDW6A)\n<!-- **If you want a video for this question please write in the comments** -->\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 900 Subscribers*\n*Current Subscribers: 799*\n\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves finding the destination city, which is the city without any outgoing path. We can approach this problem by first identifying all cities with outgoing paths. Then, among the destination cities, we find the one that has no outgoing path.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize a HashSet `cities` to store all cities with outgoing paths.\n2. Iterate through the paths and add the starting city of each path to the `cities` set.\n3. Iterate through the paths again and check the destination city of each path. If the destination city is not in the `cities` set, it means there is no outgoing path from that city, so return it as the destination city.\n\n# Complexity\n- Time complexity: The time complexity is `O(n)` because we iterate through the paths twice.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity is `O(n)` for storing the set of cities.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public String destCity(List<List<String>> paths) {\n        Set<String> cities = new HashSet<>(); \n        for (List<String> path : paths) {\n            cities.add(path.get(0)); \n        }\n        \n        for (List<String> path : paths) {\n            String dest = path.get(1); \n            if (!cities.contains(dest)) {\n                return dest; \n            }\n        }\n        return "";\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    string destCity(vector<vector<string>>& paths) {\n        unordered_set<string> cities;\n\n        // Collect outgoing cities\n        for (const auto& path : paths) {\n            cities.insert(path[0]);\n        }\n\n        // Find destination city with no outgoing path\n        for (const auto& path : paths) {\n            const std::string& dest = path[1];\n            if (cities.find(dest) == cities.end()) {\n                return dest;\n            }\n        }\n\n        return "";\n    }\n};\n```\n```Python []\nclass Solution(object):\n    def destCity(self, paths):\n        cities = set()\n\n        # Collect outgoing cities\n        for path in paths:\n            cities.add(path[0])\n\n        # Find destination city with no outgoing path\n        for path in paths:\n            dest = path[1]\n            if dest not in cities:\n                return dest\n\n        return ""\n        \n```\n```JavaScript []\n/**\n * @param {string[][]} paths\n * @return {string}\n */\nvar destCity = function(paths) {\n    const cities = new Set();\n\n        // Collect outgoing cities\n        for (const path of paths) {\n            cities.add(path[0]);\n        }\n\n        // Find destination city with no outgoing path\n        for (const path of paths) {\n            const dest = path[1];\n            if (!cities.has(dest)) {\n                return dest;\n            }\n        }\n\n        return "";\n};\n```\n![upvote.png](https://assets.leetcode.com/users/images/4603f39c-0ccd-42a9-b453-c207dde6d63d_1702607509.5376778.png)\n
['Hash Table', 'String', 'Python', 'C++', 'Java', 'JavaScript']