The problem was similar to LeetCode 815 (Bus Routes), but the interviewer explored several follow-ups involving BFS modeling, time complexity, edge cases, and reconstructing the actual travel route.
Interview Details
Coding: Minimum Number of Buses to Reach a Destination
Problem Description
Given a collection of bus routes, a starting stop source, and a destination stop destination, find the minimum number of buses required to travel from the source to the destination. Each route contains a list of stops served by a particular bus. A passenger can transfer between two routes whenever they share at least one stop. The goal is to minimize the number of distinct buses boarded, not the number of stops traveled.
If the destination cannot be reached, return -1. If the source and destination are the same, return 0.
Example
Input:
routes = [
[12, 26, 39],
[34, 39, 54, 67],
[67, 81, 96],
[26, 103]
]
source = 12
destination = 96
Output:
3
Explanation:
Take Route 0 from stop 12 to stop 39.
Transfer to Route 1 at stop 39.
Travel to stop 67 and transfer to Route 2.
Continue to stop 96.
Total buses taken = 3.
Input:
routes = [
[12, 26, 39],
[34, 39, 54, 67],
[67, 81, 96],
[26, 103]
]
source = 12
destination = 96
Output:
3
Explanation:
Take Route 0 from stop 12 to stop 39.
Transfer to Route 1 at stop 39.
Travel to stop 67 and transfer to Route 2.
Continue to stop 96.
Total buses taken = 3.
Part 1 — Graph Modeling: Treat Routes as Nodes
The first important decision was how to represent the problem as a graph. A natural approach would be to treat bus stops as graph nodes, but the question asks for the minimum number of buses rather than the shortest sequence of stops. I therefore modeled each bus route as a node, with connections between routes that share a stop.
Under this representation, moving to a new route corresponds to boarding another bus. BFS can then explore routes level by level, where each level represents the number of buses taken.
Part 2 — Build a Stop-to-Routes Mapping
The next step was to create a mapping from each stop to the routes that serve it. For the example above, some relevant entries are:
This mapping makes it possible to identify transfers efficiently. For example, Route 0 and Route 1 are connected through stop 39, while Route 1 and Route 2 are connected through stop 67. Instead of comparing every pair of routes to detect shared stops, the algorithm can use this mapping to discover neighboring routes during BFS.
Part 3 — BFS Implementation
The algorithm begins by adding all routes containing the source stop to the BFS queue. These routes represent the first bus the passenger could board, so their initial bus count is 1.
For each route removed from the queue, the algorithm visits its stops. If a stop equals the destination, the current bus count is returned; otherwise, the stop-to-routes mapping identifies possible transfers.
I used a visited set to ensure each route was added to the queue at most once. A head pointer can also be used with a Python list to avoid the repeated O(n)
Unlock Full Details
Create a free account to unlock this interview experience report.