Description

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return 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:

1Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
2Output: "Sao Paulo" 
3Explanation: 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:

1Input: paths = [["B","C"],["D","B"],["C","A"]]
2Output: "A"
3Explanation: All possible trips are: 
4"D" -> "B" -> "C" -> "A". 
5"B" -> "C" -> "A". 
6"C" -> "A". 
7"A". 
8Clearly the destination city is "A".

Example 3:

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

Constraints:

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

Solution

The constraints provide very important information about the problem. In this problem it states that paths can be upto 100 pairs. paths is never null or empty as first constraint states.

Brute Force Approach

 1class Solution {
 2    public String destCityBrute(List<List<String>> paths) {
 3        for (List<String> path: paths) {
 4            boolean isDestination = true;
 5            for (List<String> path2: paths) {
 6                if (path.get(1).equals(path2.get(0))) {
 7                    isDestination = false;
 8                    break;
 9                }
10            }
11            if (isDestination)
12                return path.get(1);
13        }
14        return null;
15    }
16}
  • Time Complexity: O(n^2)
  • Space Complexity: O(1)

Using HashMap

We can use HashMap to store origin - destination relationship. For each of the values there will be corresponding key present in this HashMap except the last destination. The last destination will not point to any destination, so it will not be present in the HashMap as a key. Now, the input paths are not sorted, so we first have to build the HashMap and have to make another pass to see which one is not present as a key.

 1class Solution {
 2    public String destCity(List<List<String>> paths) {
 3        Map<String, String> originDestinationMap = new HashMap<>();
 4        for (List<String> path: paths) {
 5            originDestinationMap.put(path.get(0), path.get(1));
 6        }
 7
 8        for (List<String> path: paths) {
 9            if (!originDestinationMap.containsKey(path.get(1)))
10                return path.get(1);
11        }
12        return null;
13    }
14}

Another approach to solve this problem is to store all origin values in a HashSet. Next, we can iterate through paths list checking if paths[i][1] is present in this HashSet. If not, that will be the final destination. Both these approaches are exactly similar in time and space complexities.

 1class Solution {
 2    public String destCity2(List<List<String>> paths) {
 3        Set<String> origins = new HashSet<>();
 4        for (List<String> path: paths) {
 5            origins.add(path.get(0));
 6        }
 7
 8        for (List<String> path: paths) {
 9            if (!origins.contains(path.get(1)))
10                return path.get(1);
11        }
12        return null;
13    }
14}
  • Time Complexity: O(n)
  • Space Complexity: O(n)