Bus Routes — BFS on Route Graph

Problem

Given bus routes (arrays of stops), find minimum number of buses to take from source to target.

Approach — BFS on Buses (not stops)

Build stop→routes map. BFS where each step boards one bus (route). From current stops, find all routes; for each route, add all its stops.

Time: O(sum of route lengths) | Space: O(same)

Solutions

Python

from collections import deque, defaultdict
class Solution:
    def numBusesToDestination(self, routes: list[list[int]], source: int, target: int) -> int:
        if source==target: return 0
        stop_to_routes=defaultdict(set)
        for i,route in enumerate(routes):
            for stop in route: stop_to_routes[stop].add(i)
        visited_stops={source}; visited_routes=set()
        q=deque([(source,0)])
        while q:
            stop,buses=q.popleft()
            for route_id in stop_to_routes[stop]:
                if route_id in visited_routes: continue
                visited_routes.add(route_id)
                for s in routes[route_id]:
                    if s==target: return buses+1
                    if s not in visited_stops:
                        visited_stops.add(s); q.append((s,buses+1))
        return -1

Complexity

Time: O(NK) where N=routes, K=avg stops per route | Space: O(NK)