< Back

1436. Destination City

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.