aboutsummaryrefslogtreecommitdiff
path: root/destination_city.py
blob: b34bfbc899b296c5c74f40914846a450c9fee21e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 1436. Destination City

"""
given the array 'paths' where 'paths[i] = [citya[i], cityb[i]]' means there
exists a direct path going from 'citya[i]' to 'cityb[i]'. 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.
"""


class Solution(object):
    def destCity(self, paths):
        """
        :type paths: List[List[str]]
        :rtype: str
        """
        cities = set()
        for i in paths:
            cities.add(i[0])
        for i in paths:
            dest = i[1]
            if dest not in cities:
                return dest
        return ""


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.destCity(
            paths=[["London", "New York"], ["New York", "Lima"], ["Lima", "Sao Paulo"]]
        )
    )
    print(obj.destCity(paths=[["B", "C"], ["D", "B"], ["C", "A"]]))