##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1436.html

# 1436. Destination City (Easy)

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
• cityA!= cityBi
• All strings consist of lowercase and uppercase English letters and the space character.

Related Topics:
String

## Solution 1.

Add all cities into a set. Remove those source cities. The one left in the set is the answer.

// OJ: https://leetcode.com/problems/destination-city/
// Time: O(N)
// Space: O(N)
class Solution {
public:
string destCity(vector<vector<string>>& paths) {
unordered_set<string> s;
for (auto &p : paths) s.insert(p[0]), s.insert(p[1]);
for (auto &p : paths) s.erase(p[0]);
return *s.begin();
}
};
• class Solution {
public String destCity(List<List<String>> paths) {
Set<String> srcSet = new HashSet<String>();
for (List<String> path : paths) {
String src = path.get(0);
}
for (List<String> path : paths) {
String dst = path.get(1);
if (!srcSet.contains(dst))
return dst;
}
return "";
}
}

############

class Solution {
public String destCity(List<List<String>> paths) {
Set<String> s = new HashSet<>();
for (var p : paths) {
}
for (var p : paths) {
if (!s.contains(p.get(1))) {
return p.get(1);
}
}
return "";
}
}

• // OJ: https://leetcode.com/problems/destination-city/
// Time: O(N)
// Space: O(N)
class Solution {
public:
string destCity(vector<vector<string>>& paths) {
unordered_set<string> s;
for (auto &p : paths) s.insert(p[0]), s.insert(p[1]);
for (auto &p : paths) s.erase(p[0]);
return *s.begin();
}
};

• class Solution:
def destCity(self, paths: List[List[str]]) -> str:
s = {a for a, _ in paths}
return next(b for _, b in paths if b not in s)

############

class Solution(object):
def destCity(self, paths):
"""
:type paths: List[List[str]]
:rtype: str
"""
starts = set()
ends = set()
for path in paths:
for end in ends:
if end not in starts:
return end
return ""

• func destCity(paths [][]string) string {
s := map[string]bool{}
for _, p := range paths {
s[p[0]] = true
}
for _, p := range paths {
if !s[p[1]] {
return p[1]
}
}
return ""
}

• function destCity(paths: string[][]): string {
const set = new Set(paths.map(([a]) => a));
for (const [_, b] of paths) {
if (!set.has(b)) {
return b;
}
}
return '';
}

• /**
* @param {string[][]} paths
* @return {string}
*/
var destCity = function (paths) {
const s = new Set();
for (const [a, _] of paths) {
}
for (const [_, b] of paths) {
if (!s.has(b)) {
return b;
}
}
return '';
};

• use std::collections::HashSet;
impl Solution {
pub fn dest_city(paths: Vec<Vec<String>>) -> String {
let set = paths.iter().map(|v| &v[0]).collect::<HashSet<&String>>();
for path in paths.iter() {
if !set.contains(&path[1]) {
return path[1].clone();
}
}
String::new()
}
}