Bus Routes - Leetcode Solution

The Bus Routes problem on Leetcode asks us to find the minimum numbers of bus we need to take to reach our destination, given the list of bus routes available and the stops they can make.

The problem can be solved using Breadth First Search (BFS) and Graph theory concepts.

Approach:

1. Create a graph where each bus stop is represented as a node and edges are drawn between two bus stops if they are covered by the same bus route. Thus, given a list of bus routes and the stops they can make, we can create a graph with this information.
2. Start BFS from the source bus stop and keep adding stops covered by the same bus route to a queue and process them till we reach the destination stop.
3. Keep track of the number of bus we take to reach the destination stop and return the minimum number.

Detailed Solution:

1. Create a Graph: To create a graph, we can use a dictionary where the key represents a bus stop and the value is a list of bus routes that cover that bus stop. We can iterate through each bus route and add its stops to the graph. Code:

from collections import defaultdict
def createGraph(routes):
    graph = defaultdict(list)
    for i, route in enumerate(routes):
        for stop in route:
            graph[stop].append(i)
    return graph

The created graph would look like:

{
    1: [0, 1],
    2: [0],
    3: [1, 2],
    4: [2]
}

where,

• node 1 is covered by bus routes 0 and 1
• node 2 is covered by bus route 0
• node 3 is covered by bus routes 1 and 2
• node 4 is covered by bus route 2

2. BFS: To perform BFS, we can start at source bus stop and add its neighbouring stops that are covered by the same bus route. We can keep a visited set to store the visited stops to avoid processing them again. We need to make sure that we are not iterating through the same bus route again and again as we can take that bus route only once during our journey. Therefore, we can use a set to keep track of bus routes that we have already taken. We can stop once we reach our destination bus stop. Code:

def bfs(graph, start, end, routes):
    queue = [(start, 0)]
    visited = set()
    busTaken = set()
    while queue:
        busStop, busCount = queue.pop(0)
        if busStop == end:
            return busCount
        for busRoute in graph[busStop]:
            if busRoute not in busTaken:
                busTaken.add(busRoute)
                for stop in routes[busRoute]:
                    if stop not in visited:
                        visited.add(stop)
                        queue.append((stop, busCount+1))
    return -1

3. Main: Now, we include both functions and take input to get the minimum number of buses needed. Code:

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

The overall time complexity of this solution is O(NM), where N is the number of bus routes and M is the average number of bus stops covered by each route. The space complexity is O(NM) as we are creating a graph of all nodes and edges.

Thus, we can get the minimum number of buses needed to reach the destination given a set of bus routes and the stops that they cover.

1