Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Bus Routes

LeetCode #815Hard
BFS over routes: each level = one more bus

Given a list of bus routes where each route is a repeating sequence of stops, return the fewest buses you must take to travel from a source stop to a target stop, or -1 if it is impossible.

Asked atAmazonGoogle
step 1 / 12
route graph — nodes are bus routes
R0{1,2,7}
R1{3,6,7}
queue of routes (FIFO)
front →
(empty)
← back
adjacency list
  • shared stop:[7 → R0,R1]
BFS where states are routes
▸
1numBusesToDest(routes, source, target):
2    build stopToRoutes: stop -> [route ids]
3    if source == target: return 0
4    queue = routes serving source, each with buses = 1
5    visited = those routes
6    while queue not empty:
7        route = queue.dequeue()      // front
8        if target in route: return buses[route]
9        for stop in route:
10            for r in stopToRoutes[stop]:
11                if r not visited:
12                    buses[r] = buses[route] + 1; enqueue r
13    return -1
state
  • routesR0{1,2,7}, R1{3,6,7}
  • source1
  • target6

line 1We want the FEWEST buses to get from stop 1 to stop 6. The trick is to make the BFS states be ROUTES, not stops: while you stay on one bus you can ride any number of stops for free, so a whole route is a single "place". Two routes are neighbours when they share a stop — that's where you can transfer. Then every BFS level = one extra bus.