Given a travel route map represented by the array paths, where paths[i] = [cityAi, cityBi] means that the route goes directly from cityAi to cityBi, find the destination city: the city with no route leading to another city.

The input guarantees that the route map forms a path with no cycles, so there is exactly one destination city.

Example 1:

Input:paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output:"Sao Paulo"
Explanation:Starting from "London", the trip finally reaches the destination city "Sao Paulo". The route is "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

Input:paths = [["B","C"],["D","B"],["C","A"]]
Output:"A"
Explanation:The possible routes are:
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly, the destination city is "A".

Example 3:

Input:paths = [["A","Z"]]
Output:"Z"

Constraints:

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• All strings consist of uppercase and lowercase English letters and spaces.

Analysis

#

The destination city has no next city to visit, so it never appears as the first element A in a pair (A, B); it appears only as a B. Therefore, store all A values in a hash set, then iterate over every B and check whether it is in the set. The first city that is not found is the answer.

Java Code

#

class Solution {
    public String destCity(List<List<String>> paths) {
        int len = paths.size();
        Set<String> set = new HashSet<>();
        paths.forEach((path) -> {
            set.add(path.get(0));
        });
        for (int i = 0; i < len; i++) {
            List<String> list = paths.get(i);
            if (!set.contains(list.get(1))) {
                return list.get(1);
            }
        }
        return null;
    }
}