## DEV Community

TK

Posted on • Originally published at leandrotk.github.io

# Algorithms Problem Solving: Destination City

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()
``````