Home

Maximum 69 Number

A hand with 8 dices Photo by Alex Chambers

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 cityBiReturn 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

Patreon Become a Patron Coffee icon Buy me a coffee