This post is part of the Algorithms Problem Solving series.
This is the Destination City problem. The description looks like this:
You are given the array
paths[i] = [cityAi, cityBi] means there exists a direct path going from
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.
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"
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]
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()