DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for Algorithms Problem Solving: Destination City
TK
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"
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

Resources

Top comments (0)

🌚 Browsing with dark mode makes you a better developer.

It's a scientific fact.