Leetcode 833 Solution

This article provides solution to leetcode question 833 (bus-routes)
Categories:
Tags:
Access this page by simply typing in "lcs 833" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/bus-routes

Solution

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0



        bus_ids = collections.defaultdict(set)
        for i, route in enumerate(routes):
            for stop in route:
                bus_ids[stop].add(i)



        q = collections.deque()
        visited = set()



        for i, route in enumerate(routes):
            if source in route:
                q.append(i)
                visited.add(i)



        step = 0
        while q:
            s = len(q)
            step += 1



            for _ in range(s):
                i = q.popleft()



                if target in routes[i]:
                    return step



                for j in routes[i]:
                    for bus_id in bus_ids[j]:
                        if bus_id in visited:
                            continue



                        q.append(bus_id)
                        visited.add(bus_id)



        return -1