Destination City

class Solution {
public:
    string findDestinationCity(vector<vector<string>>& routes) {
        unordered_set<string> citiesWithDeparture;
        for (auto& route : routes) {
            citiesWithDeparture.insert(route[0]);
        }
        
        for (auto& route : routes) {
            string target = route[1];
            if (citiesWithDeparture.find(target) == citiesWithDeparture.end()) {
                return target;
            }
        }
        
        return "";
    }
};

This solution involves finding the destination city from a given list of routes. Each route is represented as a vector of strings, where the first string is the departure city and the second is the destination city. The solution utilizes C++ and the standard library's unordered_set to efficiently determine the unique destination city that does not act as a departure city for any other route.

• Start by defining a class Solution with a public member function string findDestinationCity(vector<vector<string>>& routes).
• Create an unordered_set named citiesWithDeparture to store cities that are departure points.
• Loop through the routes array using a range-based for loop to populate the citiesWithDeparture set with the first city of each route (departure city).
• Iterate again over the routes to check each destination city:
  • For each destination city in the route list, check if it is not present in the citiesWithDeparture set.
  • If a city is found that does not exist in the citiesWithDeparture, return this city as it does not serve as a departure city and thus, is the final destination.
  • If no such city is found (though the problem context suggests there should be one), return an empty string.

This method ensures an efficient check by taking advantage of the fast look-up times of unordered sets, concluding with a solution that meets the problem's requirements.

class Solution {
    public String findDestinationCity(List<List<String>> travelPaths) {
        Set<String> origins = new HashSet<>();
        for (List<String> path : travelPaths) {
            origins.add(path.get(0));
        }
        
        for (List<String> path : travelPaths) {
            String destination = path.get(1);
            if (!origins.contains(destination)) {
                return destination;
            }
        }
        
        return "";
    }
}

The provided Java solution determines the destination city from a list of travel paths. The approach employs two main data structures: a Set called origins and a nested List called travelPaths. Each entry in travelPaths is assumed to consist of two elements — the starting city (origin) and the ending city (destination).

• Initialize a Set named origins to store each travel path's origin city. This helps in checking if a city is a starting point for any route.
• Iterate through each path in travelPaths:
  • Add the origin city of the current path to the origins set.
• Traverse the travel paths a second time:
  • For each path, check if its destination city is not in the origins set.
  • If a city appears exclusively as a destination (i.e., it is not found in the origins set), then that city is identified as the final destination. The function then returns this city.

Given the nature of the problem, if a city is not a point of origin for any path, it must be the endpoint of the series of travels. Thus, the algorithm effectively identifies the city where the journey will end based on the provided routes. In scenarios where no distinct endpoint exists, an empty string is returned as per the code. The solution provides an efficient means to pinpoint the ending city, ensuring that only cities that have never been used as a starting point are potential endpoints.

class Solution:
    def findDestination(self, routes: List[List[str]]) -> str:
        sources = set()
        for path in routes:
            sources.add(path[0])
        
        for path in routes:
            destination = path[1]
            if destination not in sources:
                return destination
        
        return ""

The provided Python solution addresses the problem of finding a destination city that you cannot travel from to any other city, given a list of city pairs representing direct paths between two cities. The solution operates in two main phases:

1. Create a set named sources to track all cities that serve as a starting point.
2. Iteratively populate the sources set with the first city from each city pair in the routes input list.

After collecting all source cities, the code performs the following steps:

1. Traverse each path in the routes list.
2. Check if the destination city (second city in each path) is not part of the sources set.
3. If a city appears only as a destination and never as a source, the code returns this city, as it is the ultimate destination city where no further travel is possible.

If no such destination city exists that isn’t a source city in any route, the function returns an empty string. This solution effectively identifies the endpoint in a series of directed paths by leveraging set operations for efficient lookup.