Bus Routes
Hard · Graphs · Array · Hash Table · Breadth-First Search
Problem
You are given routes, where routes[i] lists the stops of bus i. Each bus drives its route in a loop forever: [2, 6, 9] means the bus goes 2 → 6 → 9 → 2 → 6 and so on.
You start at stop source, not on any bus, and want to reach stop target travelling only by bus. Return the fewest buses you must board, or -1 if the target cannot be reached. If source == target, the answer is 0.
Examples
Input: routes = [[1,4,6],[6,8],[8,11,2]], source = 1, target = 2 Output: 3
Ride bus 0 to stop 6, bus 1 to stop 8, then bus 2 to stop 2.
Input: routes = [[3,5],[7,9]], source = 3, target = 9 Output: -1
No stop is shared between the two routes.
Input: routes = [[1,2,3]], source = 3, target = 1 Output: 1
The single bus passes stop 1 again after stop 3.
Constraints
- 1 <= len(routes) <= 500
- 1 <= len(routes[i]) <= 10^5
- the stops of one route are distinct
- the total number of stops over all routes is at most 10^5
- 0 <= routes[i][j] < 10^6
- 0 <= source, target < 10^6
Approaches
- Baseline: BFS over stops, one edge per pair on a route — time O(Σ Lᵢ²), Lᵢ = length of route i, space O(Σ Lᵢ²)
Follow-up
What if each bus ride also had a fare and you wanted the cheapest trip instead of the fewest buses? (The levels of BFS no longer measure cost; Dijkstra over buses does.)
Related problems
Start free on Cariara · Coding problems · System design studio
