LeetCode: 1436-Destination City Solution

Problem

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: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”

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.

Every city have a unidirectional connection, and the path of connection would walk only one time. So we can find the destination city.

---

Solution

I used a dictionary to store the city states. If city A is departure, A += 1; If city A is destination, A -= 1.

Finally, we had found the destination city state is -1. Of course you can use SET instead of dictionary.

C++ Sample Code

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        // Init
        unordered_map<string, int> counter;

        // Count
        for (vector<string>& path: paths) {
            ++counter[path[0]];
            --counter[path[1]];
        }

        // Get the destination
        for (auto& it: counter) {
            if (it.second == -1) {
                return it.first;
            }
        }

        return "";
    }
};

Python Sample Code

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        # Init
        counter = {}

        # Count
        for path in paths:
            counter[path[0]] = counter.get(path[0], 0) + 1
            counter[path[1]] = counter.get(path[1], 0) - 1

        # Find the destination
        for city in counter:
            if counter[city] == -1:
                return city

---

References

• Destination City

---

Read More

• LeetCode Note Directory