Finding the Root of a Tree (Finding the Common Destination)

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.

Hints:
Start in any city and use the path to move to the next city.
Eventually, you will reach a city with no path outgoing, this is the destination city.

Finding the Root of the Tree

Finding the common destination is equivalent as finding the root of (common ancestor) of the tree. The given input contains a list of a line segment that we can use to construct the tree. Then, we start from any of the node, iteratively traversing until we can’t go further, which is guaranteed to be the root.

The following C++ uses a hash map to store the paths between nodes. The complexity is O(N). In the best case, it only needs to go through the paths once, and in the worst case, twice (the longest path).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_map<string, string> data;
        for (const auto &n: paths) {
            data[n[0]] = n[1];
        }
        string city = paths[0][0];
        while (data.find(city) != data.end()) {
            city = data[city];
        }
        return city;
    }
};

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_map<string, string> data;
        for (const auto &n: paths) {
            data[n[0]] = n[1];
        }
        string city = paths[0][0];
        while (data.find(city) != data.end()) {
            city = data[city];
        }
        return city;
    }
};

Another algorithm is to push all the nodes into a set e.g. unordered_set. And the second time, we remove the start from the set, and remaining node in the set must be the destination.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_set<string> cities;
        for (const auto &n: paths) {
            cities.insert(n[0]);
            cities.insert(n[1]);
        }
        for (const auto &n: paths) {
            cities.erase(n[0]);
        }
        return *begin(cities);
    }
};

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_set<string> cities;
        for (const auto &n: paths) {
            cities.insert(n[0]);
            cities.insert(n[1]);
        }
        for (const auto &n: paths) {
            cities.erase(n[0]);
        }
        return *begin(cities);
    }
};

–EOF (The Ultimate Computing & Technology Blog) —