Fri. Dec 13th, 2024

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBiReturn the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips 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"
class Solution {
    public String destCity(List<List<String>> paths) {
        List<String> destCity = new ArrayList<String>();
        List<String> srcCity = new ArrayList<String>();
        
        for(List path : paths){
            for(int i=0;i<path.size();i++){
                if(i<path.size()-1) srcCity.add(path.get(i).toString());
                if(destCity.contains(path.get(i))) destCity.remove(path.get(i));
                else if(i==path.size()-1 && !srcCity.contains(path.get(i).toString())){
                    destCity.add(path.get(i).toString());
                }
            }
        }
        
        return destCity.get(0).toString();
    }
}