✅☑[C++/C/Java/Python/JavaScript] || 2 Approaches || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n#### Approach 1(Brute Force)\n1. Iterate Through Paths:\n\n    - The code i
# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n**(Also explained in the code)**\n\n#### ***Approach 1(Brute Force)***\n1. **Iterate Through Paths:**\n\n    - The code iterates through each path in the `paths` vector.\n    - It selects a candidate destination city (`candidate = paths[i][1]`) from the current path.\n1. **Check if Candidate is a Destination City:**\n\n    - It checks if the candidate city is not a starting city in any other path by comparing it with all the starting cities in each path.\n    - If the candidate is not found as a starting city in any other path (`good == true`), it\'s considered the destination city, and it\'s returned.\n1. **Return Default (If No Destination Found):**\n\n    - If no destination city is found (which shouldn\'t happen if every path is valid), the function returns an empty string `""`.\n\n# Complexity\n- *Time complexity:*\n   $$O(n^2)$$\n    \n\n- *Space complexity:*\n   $$O(1)$$\n    \n\n\n# Code\n```C++ []\n#include <vector>\n#include <string>\n\nclass Solution {\npublic:\n    // Function to find the destination city from paths\n    std::string destCity(std::vector<std::vector<std::string>>& paths) {\n        // Loop through each path\n        for (int i = 0; i < paths.size(); i++) {\n            std::string candidate = paths[i][1]; // Get the candidate destination city from the current path\n            bool good = true; // Flag to determine if the candidate is the destination city\n            \n            // Check if the candidate city is also a starting city in other paths\n            for (int j = 0; j < paths.size(); j++) {\n                if (paths[j][0] == candidate) { // If the candidate is found as a starting city in another path\n                    good = false; // Update flag to indicate it\'s not the destination city\n                    break; // Exit the loop, as we\'ve found the candidate is not the destination\n                }\n            }\n\n            if (good) {\n                return candidate; // If the candidate is not a starting city in any other path, it\'s the destination city\n            }\n        }\n        \n        return ""; // If no destination city found (shouldn\'t reach here if every path is valid)\n    }\n};\n\n\n\n```\n```C []\n#include <stdio.h>\n#include <string.h>\n\nchar* destCity(char*** paths, int pathsSize, int* pathsColSize) {\n    for (int i = 0; i < pathsSize; i++) {\n        char* candidate = paths[i][1]; // Get the candidate destination city from the current path\n        int good = 1; // Flag to determine if the candidate is the destination city\n        \n        // Check if the candidate city is also a starting city in other paths\n        for (int j = 0; j < pathsSize; j++) {\n            if (strcmp(paths[j][0], candidate) == 0) { // If the candidate is found as a starting city in another path\n                good = 0; // Update flag to indicate it\'s not the destination city\n                break; // Exit the loop, as we\'ve found the candidate is not the destination\n            }\n        }\n\n        if (good) {\n            return candidate; // If the candidate is not a starting city in any other path, it\'s the destination city\n        }\n    }\n    \n    return ""; // If no destination city found (shouldn\'t reach here if every path is valid)\n}\n\n\n\n\n```\n```Java []\nimport java.util.List;\n\nclass Solution {\n    public String destCity(List<List<String>> paths) {\n        // Loop through each path\n        for (List<String> path : paths) {\n            String candidate = path.get(1);  // Get the candidate destination city from the current path\n            boolean good = true;  // Flag to determine if the candidate is the destination city\n            \n            // Check if the candidate city is also a starting city in other paths\n            for (List<String> otherPath : paths) {\n                if (otherPath.get(0).equals(candidate)) {  // If the candidate is found as a starting city in another path\n                    good = false;  // Update flag to indicate it\'s not the destination city\n                    break;  // Exit the loop, as we\'ve found the candidate is not the destination city\n                }\n            }\n\n            if (good) {\n                return candidate;  // If the candidate is not a starting city in any other path, it\'s the destination city\n            }\n        }\n        \n        return "";  // If no destination city found (shouldn\'t reach here if every path is valid)\n    }\n}\n\n\n\n```\n```python3 []\nclass Solution:\n    def destCity(self, paths: List[List[str]]) -> str:\n        # Loop through each path\n        for path in paths:\n            candidate = path[1]  # Get the candidate destination city from the current path\n            good = True  # Flag to determine if the candidate is the destination city\n            \n            # Check if the candidate city is also a starting city in other paths\n            for other_path in paths:\n                if other_path[0] == candidate:  # If the candidate is found as a starting city in another path\n                    good = False  # Update flag to indicate it\'s not the destination city\n                    break  # Exit the loop, as we\'ve found the candidate is not the destination\n            \n            if good:\n                return candidate  # If the candidate is not a starting city in any other path, it\'s the destination city\n        \n        return ""  # If no destination city found (shouldn\'t reach here if every path is valid)\n\n\n\n```\n```javascript []\nfunction destCity(paths) {\n    for (let i = 0; i < paths.length; i++) {\n        let candidate = paths[i][1]; // Get the candidate destination city from the current path\n        let good = true; // Flag to determine if the candidate is the destination city\n        \n        // Check if the candidate city is also a starting city in other paths\n        for (let j = 0; j < paths.length; j++) {\n            if (paths[j][0] === candidate) { // If the candidate is found as a starting city in another path\n                good = false; // Update flag to indicate it\'s not the destination city\n                break; // Exit the loop, as we\'ve found the candidate is not the destination\n            }\n        }\n\n        if (good) {\n            return candidate; // If the candidate is not a starting city in any other path, it\'s the destination city\n        }\n    }\n    \n    return ""; // If no destination city found (shouldn\'t reach here if every path is valid)\n}\n\n\n```\n\n---\n\n#### ***Approach 2(Sets)***\n1. **Initialization:**\n\n    - A `set<string>` called `startCities` is initialized. This set will store all the starting cities from the paths.\n1. **Storing Starting Cities:**\n\n    - The code iterates through each path in the input `paths`.\n    - For each path, it inserts the first city (index `0` of the inner vector `path`) into the `startCities` set using `startCities.insert(path[0])`.\n1. **Finding the Destination City:**\n\n    - The code then iterates through the paths again.\n    - For each path, it checks if the destination city (index `1` of the inner vector `path`) is not found in the `startCities` set using `startCities.find(path[1]) == startCities.end()`.\n    - If the destination city is not found among the starting cities, it means it is the actual destination, so the code returns this city using `return path[1]`.\n1. **Return Default (If No Destination Found):**\n\n    - If no destination city is found (which should not happen if every path is valid), the function returns an empty string `""`.\n\n# Complexity\n- *Time complexity:*\n   $$O(n)$$\n    \n\n- *Space complexity:*\n   $$O(n)$$\n    \n\n\n# Code\n```C++ []\n\n\nclass Solution {\npublic:\n    std::string destCity(std::vector<std::vector<std::string>>& paths) {\n        set<string> startCities;\n\n        // Store all starting cities in a set\n        for (const auto& path : paths) {\n            startCities.insert(path[0]);\n        }\n\n        // Find the destination city\n        for (const auto& path : paths) {\n            if (startCities.find(path[1]) == startCities.end()) {\n                return path[1]; // Return the destination city\n            }\n        }\n\n        return ""; // If no destination city found (shouldn\'t reach here if every path is valid)\n    }\n};\n\n\n\n```\n```C []\nchar* destCity(char paths[][2], int pathsSize) {\n    char startCities[pathsSize][21]; // Assuming the maximum city name length is 20 characters\n    int startCitiesCount = 0;\n\n    // Store all starting cities in a set\n    for (int i = 0; i < pathsSize; i++) {\n        strcpy(startCities[startCitiesCount++], paths[i][0]);\n    }\n\n    // Find the destination city\n    for (int i = 0; i < pathsSize; i++) {\n        int found = 0;\n        for (int j = 0; j < startCitiesCount; j++) {\n            if (strcmp(paths[i][1], startCities[j]) == 0) {\n                found = 1;\n                break;\n            }\n        }\n        if (!found) {\n            return paths[i][1]; // Return the destination city\n        }\n    }\n\n    return ""; // If no destination city found (shouldn\'t reach here if every path is valid)\n}\n\n\n\n```\n```Java []\nimport java.util.HashSet;\nimport java.util.List;\nimport java.util.Set;\n\nclass Solution {\n    public String destCity(List<List<String>> paths) {\n        Set<String> startCities = new HashSet<>();\n\n        // Store all starting cities in a set\n        for (List<String> path : paths) {\n            startCities.add(path.get(0));\n        }\n\n        // Find the destination city\n        for (List<String> path : paths) {\n            if (!startCities.contains(path.get(1))) {\n                return path.get(1); // Return the destination city\n            }\n        }\n\n        return ""; // If no destination city found (shouldn\'t reach here if every path is valid)\n    }\n}\n\n\n\n```\n```python3 []\nclass Solution:\n    def destCity(self, paths: List[List[str]]) -> str:\n        start_cities = set()\n\n        # Store all starting cities in a set\n        for path in paths:\n            start_cities.add(path[0])\n\n        # Find the destination city\n        for path in paths:\n            if path[1] not in start_cities:\n                return path[1]  # Return the destination city\n\n        return ""  # If no destination city found (shouldn\'t reach here if every path is valid)\n\n\n\n```\n```javascript []\nfunction destCity(paths) {\n    const startCities = new Set();\n\n    // Store all starting cities in a set\n    for (const path of paths) {\n        startCities.add(path[0]);\n    }\n\n    // Find the destination city\n    for (const path of paths) {\n        if (!startCities.has(path[1])) {\n            return path[1]; // Return the destination city\n        }\n    }\n\n    return ""; // If no destination city found (shouldn\'t reach here if every path is valid)\n}\n\n\n```\n\n---\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Hash Table', 'String', 'C', 'C++', 'Java', 'Python3', 'JavaScript']