Bus Routes
Real-world version: Fewest Loops to the DockThe statement here is our own: the same inputs, outputs and technique.
A hospital campus is served by a fixed set of shuttle loops. Loop i calls at the docks listed in loops[i], cycling through them again and again without ever stopping.
A courier standing at a dock may board any loop that calls at that dock, stay aboard as long as they like, and step off at any other dock the loop calls at. Moving from one loop to another is only possible at a dock the two loops have in common, and the courier is not allowed to walk between docks.
The courier begins at dock start and needs to reach dock finish. Return the fewest loops the courier must board. When the courier is already standing at finish, the answer is 0. When no chain of loops joins the two docks, return -1.
Within a single loop every dock number is listed once, but two loops may well share docks. Dock numbers are only labels, so a number that appears in no loop simply has no shuttle service.
Examples
Example 1
- Input
- loops = [[4, 8, 12], [12, 20, 5]], start = 4, finish = 5
- Output
- 2
Board the first loop at dock 4 and ride to dock 12, which both loops call at, then board the second loop there and ride to dock 5.
Example 2
- Input
- loops = [[3, 9], [11, 14]], start = 3, finish = 14
- Output
- -1
The two loops share no dock, so a courier who boards at dock 3 can never reach dock 14.
Example 3
- Input
- loops = [[7, 2, 5]], start = 5, finish = 5
- Output
- 0
The courier is already where they need to be, so no shuttle is boarded at all.
Constraints
- 1 <= loops.length <= 500
- 1 <= loops[i].length <= 10^5
- Every dock number inside one loop is distinct
- The total number of dock entries across all loops is at most 10^5
- 0 <= loops[i][j] < 10^6
- 0 <= start, finish < 10^6
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def fewest_loops(loops: list[list[int]], start: int, finish: int) -> int:public int fewestLoops(int[][] loops, int start, int finish)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's