LeetCode 1436: Destination City

Explanation

To find the destination city, we can create a set of all cities that are the starting point of a path. Then we iterate through all the cities in the paths array and check if they are not in the set of starting cities. The city that is not a starting city is the destination city.

Algorithm:

1. Create a set to store starting cities.
2. Iterate through the paths array and add the first city of each path to the set.
3. Iterate through the paths array again and check if the second city of each path is not in the set of starting cities. This city is the destination city.

Time Complexity: O(n), where n is the number of paths.

Space Complexity: O(n), to store the set of starting cities.

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