Lc1436

class Solution:
    # time& space O(N) 
    def destCity(self, paths: List[List[str]]) -> str:
        if len(paths) == 1 :
            return paths[0][1]
        # step1, set up start_dic 
        start_d = dict()
        # step2, iterate path in paths, check if destination in the path is a start in another path
        for path in paths:
            start_d[path[0]] = path
        # if not exist, return 
        for path in paths:
            dest = path[1]
            if dest not in start_d:
                return dest

# main idea to use set and remove items in desti set that appeared in start set 
class Solution:
    # time& space O(N) 
    def destCity(self, paths: List[List[str]]) -> str:
            return (set([path[1] for path in paths]) - set([path[0] for path in paths])).pop()