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.

Examples

Example 1

1
2
3

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

1
2
3
4
5
6
7
8

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

1
2

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.

Solution

Method 1 – Hash Set for Outgoing Cities

Intuition

The destination city is the only city that never appears as a starting point in any path. If we collect all cities that have outgoing paths, the destination city will be the one that is never in this set.

Approach

  1. Create a set to store all cities that have outgoing paths (i.e., all cityAi).
  2. Iterate through all paths and add each cityAi to the set.
  3. Iterate through all cityBi (destination cities in each path).
  4. The city that is not in the outgoing set is the destination city.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_set<string> out;
        for (auto &p : paths) out.insert(p[0]);
        for (auto &p : paths) if (!out.count(p[1])) return p[1];
        return "";
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func destCity(paths [][]string) string {
    out := make(map[string]bool)
    for _, p := range paths {
        out[p[0]] = true
    }
    for _, p := range paths {
        if !out[p[1]] {
            return p[1]
        }
    }
    return ""
}
1
2
3
4
5
6
7
8

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> out = new HashSet<>();
        for (List<String> p : paths) out.add(p.get(0));
        for (List<String> p : paths) if (!out.contains(p.get(1))) return p.get(1);
        return "";
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun destCity(paths: List<List<String>>): String {
        val out = mutableSetOf<String>()
        for (p in paths) out.add(p[0])
        for (p in paths) if (p[1] !in out) return p[1]
        return ""
    }
}
1
2
3
4
5
6
7

class Solution:
    def destCity(self, paths: list[list[str]]) -> str:
        out = set(p[0] for p in paths)
        for p in paths:
            if p[1] not in out:
                return p[1]
        return ""
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn dest_city(paths: Vec<Vec<String>>) -> String {
        use std::collections::HashSet;
        let mut out = HashSet::new();
        for p in &paths {
            out.insert(&p[0]);
        }
        for p in &paths {
            if !out.contains(&p[1]) {
                return p[1].clone();
            }
        }
        "".to_string()
    }
}
1
2
3
4
5
6
7
8

class Solution {
    destCity(paths: string[][]): string {
        const out = new Set<string>();
        for (const p of paths) out.add(p[0]);
        for (const p of paths) if (!out.has(p[1])) return p[1];
        return '';
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of paths. We iterate through the paths twice.
  • 🧺 Space complexity: O(n), for storing the set of outgoing cities.