# [LeetCode]#1436. Destination City

**Environment: Python 3.7**

**Key technique: collections.defaultdict, Hash Table**

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 2:**

**Input:** paths = [["B","C"],["D","B"],["C","A"]]

**Output:** "A"

**Analysis:**

- Create Hash Table for path
- Search all string list in Hash Table
- If string doesn’t have pair, return it.

**Solution:**

import collections

class Solution:

def destCity(self, paths):hashtable = collections.defaultdict(str)

ls = []

for a,b in paths:

hashtable[a] = b

ls += a,

ls += b,

for ans in ls:

if hashtable[ans] == "":

return ans

**Submissions:**

**Reference:**