Given a list of paths where paths[0] is the starting city and paths[0] is the destination city, return the only city that is never a starting city, only a destination.
To solve this we just use list comprehension to extract the start and destination cities, placing them each into two seperate sets. Then we use a set operation to calculate the difference between the destinations and the starts, returning the only city that is the only destination.
The solution is as follows:
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
starts = set([start for start, _ in paths])
destinations = set([destination for _, destination in paths])
return list(destinations - starts)[0]_ Time Complexity:
O(n) - We parse all paths.
_ Space Complexity:
O(n) - We create two sets of starts and destinations.