Stokastik

Machine Learning, AI and Programming

LeetCode : Bus Routes

Problem Statement

Solution :

Observe that one can switch from one route to another route, if both the routes have at-least one stop in common. Starting with the source stop S, there could be multiple possible bus routes R that includes this stop. Thus for every possible route R that include the stop S, do a Breadth First Search to all possible routes R' reachable from this route. R' can be same as R.

For example, if two routes are [1,2,7] and [3,6,7], then one can switch from one to another since there is a common stop 7 between these two.

If for possible route R', if this route includes the destination stop T, then we are done, else we continue to do BFS from each possible route R', until we either find a route with the stop T or have exhausted searching all possible routes and did not find any route with T in it.

The minimum number of routes to traverse in the BFS, gives the solution for a particular starting route R. Simply take the minimum over all possible starting route R, to find the final solution.

Here is the Python code :

import collections
class Solution(object):
def take_bus(self, route_set, rr_map, curr_route, dest):
queue = [(curr_route, 1)]
visited = set([curr_route])
while len(queue) > 0:
route, depth = queue.pop()
if dest in route_set[route]:
return depth
else:
possible_routes = rr_map[route]
for rt in possible_routes:
if rt not in visited:
visited.add(rt)
queue.insert(0, (rt, depth + 1))
return len(route_set) + 1
def numBusesToDestination(self, routes, S, T):
if S == T:
return 0
rr_map = collections.defaultdict(set)
route_set = []
for route in routes:
route_set.append(set(route))
for i in range(len(route_set)):
for j in range(len(route_set)):
if i != j:
x, y = route_set[i], route_set[j]
if len(x.intersection(y)) > 0:
rr_map[i].add(j)
rr_map[j].add(i)
source_routes = []
for idx in range(len(route_set)):
x = route_set[idx]
if S in x:
source_routes.append(idx)
min_num_buses = len(route_set) + 1
for s_route in source_routes:
min_num_buses = min(min_num_buses, self.take_bus(route_set, rr_map, s_route, T))
if min_num_buses == len(route_set) + 1:
return -1
return min_num_buses

The function 'take_bus' performs BFS starting at a particular route until we find a route with the destination or exhaust all possible routes. The algorithm uses Queue approach instead of recursion.

The variable 'rr_map' is map from each route R to all possible routes R' reachable from R according to our earlier definition.

To make searching destination stop T in one of the routes more efficient, we convert each route into a set. If there are N routes, each containing M stops, then total run time to convert each route into a set is O(NM). Searching for a stop T in a route set is O(logM) or O(1) depending on whether set is implemented as a tree or a hash-table.

There could maximum of N possible starting routes for source S. Each BFS step searches O(N) routes. Thus the worst case time complexity for each step is O(N*logM).

Total run time complexity is O(N2*logM) + O(NM).

Categories: PROBLEM SOLVING

Tags: , , ,