Fewest line changes: hints, no solution
Medium · Graphs
A city runs several transit lines. Each row of lines lists the stations that one line serves, in no particular order. A passenger can ride a line between any two of its stations without changing, and can change to another line at any station that both lines serve.
Given an origin station and a destination station, return the smallest number of line changes needed to travel from one to the other. Riding a single line the whole way needs 0 changes. If they are the same station, return 0. If the trip is impossible, or a station is on no line, return -1. Station ids are non-negative and can be large, so they are not indexes.
Examples
- Input
- lines = [[0, 1, 2], [2, 3, 4], [4, 5]], origin = 0, target = 5
- Output
- 2
- Note
- Change at station 2 and again at station 4, so two changes.
- Input
- lines = [[0, 1, 2], [2, 3, 4], [4, 5]], origin = 0, target = 2
- Output
- 0
- Note
- Stations 0 and 2 share the first line, so no change is needed.
- Input
- lines = [[1, 2], [3, 4]], origin = 1, target = 4
- Output
- -1
- Note
- The two lines share no station, so the trip is impossible.
Constraints
- 1 <= lines.length <= 60000
- Every line lists 1 to 10 stations, ids from 0 to 1000000
- Line rows may repeat a station
Hint 1: a nudge
Count what you are trying to minimise: is it stations visited or times you step off one line onto another? Which of those does the passenger actually care about here?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.