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

# 1436. Destination City (Easy)

You are given the array `paths`

, where `paths[i] = [cityA`

means there exists a direct path going from _{i}, cityB_{i}]`cityA`

to _{i}`cityB`

. _{i}*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 <= cityA`

_{i}.length, cityB_{i}.length <= 10`cityA`

_{i }!= cityB_{i}- 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();
}
};
```

Java

```
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);
srcSet.add(src);
}
for (List<String> path : paths) {
String dst = path.get(1);
if (!srcSet.contains(dst))
return dst;
}
return "";
}
}
```