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()
Resources
- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Stack Data Structure
- Queue Data Structure
- Linked List
- Tree Data Structure
Have fun, keep learning, and always keep coding!