💯Faster✅💯 Lesser✅3 Methods🔥Using Set Operations🔥Using HashSet🔥Using Lists🔥Python🐍Java☕C++✅C📈
\uD83D\uDE80 Hi, I\'m Mohammed Raziullah Ansari, and I\'m excited to share 3 ways to solve this question with detailed explanation of each approach:\n\n# Proble
# \uD83D\uDE80 Hi, I\'m [Mohammed Raziullah Ansari](https://leetcode.com/Mohammed_Raziullah_Ansari/), and I\'m excited to share 3 ways to solve this question with detailed explanation of each approach:\n\n# Problem Explaination: \nThe `Destination City` problem typically involves a scenario where you are given a list of pairs of cities, and each pair represents a direct connection from one city to another. The task is to find the destination city, which is the city that is not the source in any pair.\n\n# \uD83D\uDD0D Methods To Solve This Problem:\nI\'ll be covering three different methods to solve this problem:\n1. Using HashSet\n2. Using Lists\n3. Using Set Operations\n\n# 1. Using HashSet: \n- Create a HashSet to store the set of source cities.\n- Iterate through the list of pairs and add each source city to the HashSet.\n- Iterate through the list of pairs again and check for the destination city that is not in the HashSet.\n# Complexity\n- \u23F1\uFE0F Time Complexity: `O(n)` where n is the number of pairs in the list.\n\n- \uD83D\uDE80 Space Complexity: `O(n)` for the HashSet.\n\n# Code\n```Python []\nclass Solution:\n    def destCity(self, paths: List[List[str]]) -> str:\n        source_cities = set()\n        for path in paths:\n            source_cities.add(path[0])\n        for path in paths:\n            if path[1] not in source_cities:\n                return path[1]\n```\n```Java []\nclass Solution {\n    public String destCity(List<List<String>> paths) {\n        Set<String> sourceCities = new HashSet<>();\n        for (List<String> path : paths) {\n            sourceCities.add(path.get(0));\n        }\n        for (List<String> path : paths) {\n            if (!sourceCities.contains(path.get(1))) {\n                return path.get(1);\n            }\n        }\n        \n        return "";\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    string destCity(vector<vector<string>>& paths) {\n        unordered_set<string> sourceCities;\n        for (const auto& path : paths) {\n            sourceCities.insert(path[0]);\n        }\n        for (const auto& path : paths) {\n            if (sourceCities.find(path[1]) == sourceCities.end()) {\n                return path[1];\n            }\n        }\n        return "";\n    }\n};\n\n```\n```C []\nchar* destCity(char*** paths, int pathsSize, int* pathsColSize) {\n    char** sourceCities = (char**)malloc(pathsSize * sizeof(char*));\n    for (int i = 0; i < pathsSize; ++i) {\n        sourceCities[i] = paths[i][0];\n    }\n    for (int i = 0; i < pathsSize; ++i) {\n        int j;\n        for (j = 0; j < pathsSize; ++j) {\n            if (strcmp(paths[i][1], sourceCities[j]) == 0) {\n                break;\n            }\n        }\n        if (j == pathsSize) {\n            return paths[i][1];\n        }\n    }\n    \n    return "";\n}\n\n```\n# 2. Using Lists:\n- Create two lists - one for source cities and one for destination cities.\n- Iterate through the list of pairs and add each source and destination city to their respective lists.\n- Find the destination city that does not appear in the source cities list.\n# Complexity\n- \u23F1\uFE0F Time Complexity: `O(n)` where n is the number of pairs in the list.\n\n- \uD83D\uDE80 Space Complexity: `O(n)` for the two lists.\n\n# Code\n```Python []\nclass Solution:\n    def destCity(self, paths: List[List[str]]) -> str:\n        source_cities = set()\n        destination_cities = set()\n        for path in paths:\n            source_cities.add(path[0])\n            destination_cities.add(path[1])\n        for city in destination_cities:\n            if city not in source_cities:\n                return city\n```\n```Java []\nclass Solution {\n    public String destCity(List<List<String>> paths) {\n        Set<String> sourceCities = new HashSet<>();\n        Set<String> destinationCities = new HashSet<>();\n        for (List<String> path : paths) {\n            sourceCities.add(path.get(0));\n            destinationCities.add(path.get(1));\n        }\n        for (String city : destinationCities) {\n            if (!sourceCities.contains(city)) {\n                return city;\n            }\n        }\n        return null;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    std::string destCity(std::vector<std::vector<std::string>>& paths) {\n        unordered_set<string> sourceCities;\n        unordered_set<string> destinationCities;\n        for (const auto& path : paths) {\n            sourceCities.insert(path[0]);\n            destinationCities.insert(path[1]);\n        }\n        for (const auto& city : destinationCities) {\n            if (sourceCities.find(city) == sourceCities.end()) {\n                return city;\n            }\n        }\n        return "";\n    }\n};\n```\n```C []\nchar* destCity(char*** paths, int pathsSize, int* pathsColSize) {\n    char** sourceCities = (char**)malloc(pathsSize * sizeof(char*));\n    char** destinationCities = (char**)malloc(pathsSize * sizeof(char*));\n    for (int i = 0; i < pathsSize; ++i) {\n        sourceCities[i] = paths[i][0];\n        destinationCities[i] = paths[i][1];\n    }\n    for (int i = 0; i < pathsSize; ++i) {\n        int j;\n        for (j = 0; j < pathsSize; ++j) {\n            if (i != j && strcmp(destinationCities[i], sourceCities[j]) == 0) {\n                break;\n            }\n        }\n        if (j == pathsSize) {\n            return destinationCities[i];\n        }\n    }\n    return NULL;\n}\n```\n# 3. Using Set Operations:\n   - Create a set of source cities.\n- Create a set of destination cities.\n- Find the difference between the two sets to get the destination city.\n# Complexity\n- \u23F1\uFE0F Time Complexity: `O(n)` where n is the number of pairs in the list.\n\n- \uD83D\uDE80 Space Complexity: `O(n)` for the two sets.\n\n# Code\n```Python []\nclass Solution:\n    def destCity(self, paths: List[List[str]]) -> str:\n        source_cities = set()\n        destination_cities = set()\n        \n        for path in paths:\n            source_cities.add(path[0])\n            destination_cities.add(path[1])\n        result = destination_cities - source_cities\n        return result.pop()\n```\n```Java []\nclass Solution {\n    public String destCity(List<List<String>> paths) {\n        Set<String> sourceCities = new HashSet<>();\n        Set<String> destinationCities = new HashSet<>();\n        for (List<String> path : paths) {\n            sourceCities.add(path.get(0));\n            destinationCities.add(path.get(1));\n        }\n        destinationCities.removeAll(sourceCities);\n        return destinationCities.iterator().next();\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    string destCity(vector<vector<string>>& paths) {\n        unordered_set<string> sourceCities;\n        unordered_set<string> destinationCities;\n        for (const auto& path : paths) {\n            sourceCities.insert(path[0]);\n            destinationCities.insert(path[1]);\n        }\n        for (const auto& city : destinationCities) {\n            if (sourceCities.find(city) == sourceCities.end()) {\n                return city;\n            }\n        }\n        return "";\n    }\n};\n\n```\n```C []\nchar* destCity(char*** paths, int pathsSize, int* pathsColSize) {\n    char* sourceCities[pathsSize];\n    char* destinationCities[pathsSize];\n    for (int i = 0; i < pathsSize; ++i) {\n        sourceCities[i] = paths[i][0];\n        destinationCities[i] = paths[i][1];\n    }\n    for (int i = 0; i < pathsSize; ++i) {\n        int found = 0;\n        for (int j = 0; j < pathsSize; ++j) {\n            if (strcmp(destinationCities[i], sourceCities[j]) == 0) {\n                found = 1;\n                break;\n            }\n        }\n        if (!found) {\n            return destinationCities[i];\n        }\n    }\n    return ""; \n}\n\n```\n# \uD83C\uDFC6Conclusion: \nwe explored three effective methods to solve the "Destination City" problem, which involves finding the destination city in a list of pairs representing direct connections between cities. Each method provides a different approach to tackle the problem.\n\n# \uD83D\uDCA1 I invite you to check out my profile for detailed explanations and code for each method. Happy coding and learning! \uD83D\uDCDA
['Hash Table', 'String', 'C', 'Ordered Set', 'C++', 'Java', 'Python3']