Problem statement

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

Solution

Idea here is to work with buses, not with stops. Let n be number of buses and x1, x2, ..., xn be number of stops in paths. Then, let us first create for each unique stop list of buses, which visit this stop in O(x1 + ... + xn), then for each stop we create all pairs of transfers.

Complexity

Theoretically complexity is O((x1 + ... + xn) * n^2), but in practice it is usually much less. Space complexity is O(n^2). Good question, if we can reduce the biggest part of complexity to make it smaller? Space complexity is O(n^2)

Code

class Solution:
    def numBusesToDestination(self, routes, S, T):
        if S == T: return 0
        
        stops = defaultdict(set)  #stops -> list of buses
        for i, route in enumerate(routes):
            for stop in route:
                stops[stop].add(i)
                
        transfers = defaultdict(set)
        for i in stops:
            for st1, st2 in permutations(stops[i], 2):
                transfers[st1].add(st2)
                
        beg, end = stops[S], stops[T]
        queue = deque((1, i) for i in beg)
        visited = set([0])
        
        while queue:
            steps, bus = queue.popleft()
            if bus in end: return steps
            for neib in transfers[bus]:
                if neib not in visited:
                    visited.add(neib)
                    queue.append((steps + 1, neib))
                    
        return -1

Remark

There are a bit different ways how we can perform bfs, we can do it on stations as well.