This post is part of the Algorithms Problem Solving series.

## Problem description

This is the Destination City problem. The description looks like this:

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

```
Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo"
Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Input: paths = [["A","Z"]]
Output: "Z"
```

## Solution

My first approach is to get all the origins and destinations in different lists and the get the first difference between the lists.

```
def dest_city(paths):
all_origins = []
all_destinations = []
for [city1, city2] in paths:
all_origins.append(city1)
all_destinations.append(city2)
return [d for d in all_destinations if d not in all_origins][0]
```

We can also use the `set`

data structure to use the difference operation:

```
def dest_city(paths):
all_origins = set()
all_destinations = set()
for [city1, city2] in paths:
all_origins.add(city1)
all_destinations.add(city2)
return (all_destinations - all_origins).pop()
```

## Top comments (0)