How do you solve Bus Routes?

Construct a mapping from each stop to the list of buses that visit it. Use a BFS queue initialized with the source stop. At each BFS layer, increment the bus count and explore all buses reachable from the current stops that have not been used yet. For each such bus, enqueue all its stops that have not been visited. If the target stop is found during this process, return the current bus count. If BFS completes without finding the target, return -1.

What pattern does Bus Routes use?

The Pattern: BFS (Shortest Path on Unweighted Graph) The Heuristic: When the problem asks for the minimum number of steps or transitions in a network with uniform edge cost, model the problem as a graph and use BFS to explore layer by layer, ensuring the first time you reach the target is the shortest path.

Bus Routes — BFS

Q: What is the time complexity of Bus Routes?

O(N + E). Building the stop-to-bus mapping takes O(N) where N is the total number of stops across all routes. BFS explores each stop and bus at most once, resulting in O(N + E) time, where E is the total number of edges (bus-stop connections).

Problem

Given a list of bus routes where each route is a list of stops, and two stops source and target, return the minimum number of buses one must take to travel from source to target. Return -1 if it is not possible.

1 ≤ routes.length ≤ 500
1 ≤ routes[i].length ≤ 10⁵
0 ≤ routes[i][j] < 10⁶
0 ≤ source, target < 10⁶

Example

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6

Output: 2

Starting at stop 1, take the first bus (route 0) which visits stops 1, 2, and 7. At stop 7, transfer to the second bus (route 1) which visits stops 3, 6, and 7. This requires taking 2 buses in total. The BFS explores stops reachable by taking buses from the source, expanding layer by layer until the target stop is found.

Approach

Straightforward Solution

A brute-force approach would attempt to explore all possible sequences of stops and buses, which is computationally infeasible due to the large input size and potential cycles.

Core Observation

The problem can be viewed as a graph traversal where nodes are bus stops and edges represent the ability to travel between stops via a bus route. The goal is to find the shortest path in terms of number of buses taken, not stops visited.

Path to Optimal

Preview

The key insight is to use Breadth-First Search (BFS) starting from the source stop, exploring all stops reachable by taking one bus, then all stops reachable by taking two buses, and so forth…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Construct a mapping from each stop to the list of buses that visit it. Use a BFS queue initialized with the source stop…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(N + E)

Building the stop-to-bus mapping takes O(N) where N is the total number of stops across all routes. BFS explores each stop and bus at most once, resulting in O(N + E) time, where E is the total number of edges (bus-stop connections).

Space

O(N + E)

The stop-to-bus mapping and BFS queue require O(N + E) space, where N is the number of stops and E is the number of bus-stop edges. The visited sets for stops and buses also scale with input size.

Solution

Python

1class Solution:
  def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
      if source == target:
          return 0
5
      stop_to_buses = defaultdict(list)
      for bus, stops in enumerate(routes):
          for stop in stops:
              stop_to_buses[stop].append(bus)
10
      queue = deque([source])
      visited_stops = {source}
      used_buses = set()
      buses_taken = 0
15
      while queue:
          buses_taken += 1
18
          for _ in range(len(queue)):
              stop = queue.popleft()
21
              for bus in stop_to_buses[stop]:
                  if bus in used_buses:
                      continue
25
                  used_buses.add(bus)
27
                  for next_stop in routes[bus]:
                      if next_stop == target:
                          return buses_taken
31
                      if next_stop not in visited_stops:
                          visited_stops.add(next_stop)
                          queue.append(next_stop)
35
      return -1

Step-by-Step Solution

1

Build Stop-to-Bus Mapping to Enable Fast Bus Lookup

6stop_to_buses = defaultdict(list)
7for bus, stops in enumerate(routes):
8    for stop in stops:
9        stop_to_buses[stop].append(bus)

Objective

To create a mapping from each stop to the list of buses that visit it, enabling quick lookup of buses available at any stop.

Key Insight

Directly searching which buses can be taken from a stop is expensive without indexing. By precomputing a dictionary mapping stops to buses, the algorithm can instantly find all buses accessible from any stop during BFS traversal, reducing redundant searches and improving efficiency.

Interview Quick-Check

Core Logic

The stop-to-bus mapping transforms the problem into a graph where edges connect stops to buses, enabling BFS to traverse stops via buses efficiently.

Common Pitfalls & Bugs

Failing to build this mapping leads to repeated scanning of all routes for each stop, causing timeouts.

2

Initialize BFS State with Source Stop and Tracking Structures

To set up the BFS queue starting from the source stop and initialize visited sets for stops and buses to avoid revisiting.

3

Perform BFS to Explore Stops Layer by Layer by Taking Buses

To iteratively explore stops reachable by taking an increasing number of buses, returning the bus count when the target stop is found.

4

Return -1 if Target Stop is Unreachable

To return -1 when BFS completes without finding the target stop, indicating no possible route.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 29 Critical

if next_stop == target:

Check if the next stop is the target stop.

Finding the target stop means the shortest path in terms of buses taken has been found, allowing immediate return.

Line 30 Critical

return buses_taken

Return the current bus count as the minimum buses needed.

Returning immediately upon finding the target stop ensures the BFS shortest path property is preserved and the minimal bus count is returned.

Line 9 Critical

stop_to_buses[stop].append(bus)

Append the current bus to the list of buses for this stop.

This line populates the stop-to-bus mapping, enabling quick access to buses from any stop during BFS.

Full line-by-line criticality + rationale for all 25 lines available on Pro.

Test Your Understanding

Why does BFS guarantee the minimum number of buses taken to reach the target stop?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Bus Routes from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Bus Routes drill

or drill a free problem

1	`class Solution:`
2	`def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:`
3	`if source == target:`
4	`return 0`
5
6	`stop_to_buses = defaultdict(list)`
7	`for bus, stops in enumerate(routes):`
8	`for stop in stops:`
9	`stop_to_buses[stop].append(bus)`
10
11	`queue = deque([source])`
12	`visited_stops = {source}`
13	`used_buses = set()`
14	`buses_taken = 0`
15
16	`while queue:`
17	`buses_taken += 1`
18
19	`for _ in range(len(queue)):`
20	`stop = queue.popleft()`
21
22	`for bus in stop_to_buses[stop]:`
23	`if bus in used_buses:`
24	`continue`
25
26	`used_buses.add(bus)`
27
28	`for next_stop in routes[bus]:`
29	`if next_stop == target:`
30	`return buses_taken`
31
32	`if next_stop not in visited_stops:`
33	`visited_stops.add(next_stop)`
34	`queue.append(next_stop)`
35
36	`return -1`

6	`stop_to_buses = defaultdict(list)`
7	`for bus, stops in enumerate(routes):`
8	`for stop in stops:`
9	`stop_to_buses[stop].append(bus)`