Fewest Bus Rides
HardGraphs
Problem
A city runs buses on loop lines: routes[i] lists the stops of line i, and a bus on that line visits all of them over and over. You can board or leave any bus at any of its stops.
Starting at stop source and travelling only by bus, return the minimum number of buses you must board to reach stop target. Return 0 if source == target, and -1 if the target cannot be reached.
Example 1
- Input:
- routes = [[1,4,6],[6,9],[9,12,2]], source = 1, target = 12
- Output:
- 3
Board line 0 to stop 6, line 1 to stop 9, then line 2 to stop 12.
Example 2
- Input:
- routes = [[3,5,8],[8,10]], source = 3, target = 10
- Output:
- 2
Constraints
- 1 ≤ routes.length ≤ 500
- 1 ≤ routes[i].length ≤ 10^4
- Total stops over all lines ≤ 10^5
- 0 ≤ stop numbers, source, target < 10^6
Hint
Show the first hint
Counting stops is the wrong measure: what you pay for is each bus you board.
Walkthrough
How to approach it
01Clarify before coding
- Does staying on one bus for many stops count once? Yes, one boarding = one ride.
- What if source equals target? 0, even if no line serves it.
- Can stop numbers be large and sparse? Yes, up to 10^6, so use a hash map rather than an array per stop.
02Brute force
BFS over stops, with an edge between every two stops on the same line.
Cost: A line with s stops creates s² edges: 10^8 edges for one line of 10^4 stops.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.