FunctionRacerProblemsRace

Fewest Buses

HardGraphsPython, JavaScript, TypeScript, Java, C++

A town has several bus lines. routes[i] lists the stops of line i; its buses drive round these stops again and again, so on one bus you can ride from any stop of the line to any other.

You are at stop source and want to get to stop target, changing lines only at a stop that both lines share. Return the fewest buses you must board, or -1 if target cannot be reached. If you are already there, the answer is 0.

Example 1

routes [[2,5,8],[8,4],[4,9,1]]
source 2
target 1
returns 3

Line 0 to stop 8, line 1 to stop 4, line 2 to stop 1: three buses.

Example 2

routes [[1,2],[3,4]]
source 1
target 4
returns -1

The two lines share no stop.

Example 3

routes [[2,5,8],[8,4],[4,9,1]]
source 5
target 8
returns 1

Stops 5 and 8 are both on line 0.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems