[Python] 2 Set. 1 Line. 2 Loops. O(n) time, O(n) space, Code, Explanation
\nKey Idea\nSmart way: Add destination cities into a set and remove source cities from set.\n\nWhy smart way works\nYou want to find a city which will not go an
\n**Key Idea**\nSmart way: Add destination cities into a set and remove source cities from set.\n\n**Why smart way works**\nYou want to find a city which will not go anywhere, so that city would never come into source cities i.e. `paths[i][0]` for all `i`.\nEvery other city will certainly appear once in source `paths[i][0]` for all `i`.\n\nHence, if you add all `paths[i][1]` into a set and remove `paths[i][0]` for all `i`\'s, it will eventually have just one value.\n\n**Complexity Analysis**\nIf there are `n` paths, there would be at most `n` insertions into the set. and simmilarly `n` removals.\nHence space required would `O(n)`.\nEach insertion/removal would take constant time, so time complexity `O(n)`.\n\nHope this helps!\nPlease upvote if you like it.\n\n```\nclass Solution(object):\n    def destCity(self, paths):\n        return (set([path[1] for path in paths]) - set([path[0] for path in paths])).pop()\n```
[]