0% completed
Problem Statement
You are given an array routes
where routes[i]
is the list of bus stops that the i<sup>the</sup> bus travels in a cyclic manner. For example, if routes[0] = [2, 3, 7]
, it means that bus 0 travels through the stops 2 -> 3 -> 7 -> 2 -> 3 -> 7 ... and then repeats this sequence indefinitely.
You start at a bus stop called source
and wish to travel to a bus stop called target
using the bus routes. You can switch
buses at any bus stop that is common to the routes of two buses.
Return the minimum
number of buses you need to take to travel from source
to target
. If it is not possible to reach the target, return -1
.
Examples
Example 1
- Input: routes =
[[2, 3, 4], [5, 6, 7, 8], [4, 5, 9, 10], [10, 12]]
, source =3
, target =12
- Expected Output:
3
- Justification: Start at stop
3
, take bus0
to stop4
, switch to bus2
to reach stop10
, and then take bus3
to reach to12
. You need 3 buses.
Example 2
- Input: routes =
[[1, 2, 3, 4, 5], [5, 6, 7, 8], [8, 9, 10, 11]]
, source =1
, target =11
- Expected Output:
3
- Justification: Start at stop
1
, take bus0
to stop5
, switch to bus1
to reach stop8
, then switch to bus2
to reach stop11
. You need 3 buses.
Example 3
- Input: routes =
[[1, 2, 5], [3, 6, 7], [7, 9, 10]]
, source =2
, target =10
- Expected Output:
-1
- Justification: It is not possible to reach from bus stop
2
to10
.
Constraints:
- 1 <= routes.length <= 500.
- 1 <= routes[i].length <= 10<sup>5</sup>
- All the values of routes[i] are unique.
- sum(routes[i].length) <= 10<sup>5</sup>
- 0 <= routes[i][j] < 10<sup>6</sup>
- 0 <= source, target < 10<sup>6</sup>
Solution
To solve this problem, we can use the Breadth-First Search (BFS) algorithm. The problem requires us to find the shortest path in terms of bus transfers from the source to the target stop. BFS is suitable because it explores all possible routes level by level, ensuring that we find the shortest path first.
We'll start from the source stop and explore all buses that can be taken from there. For each bus, we'll check all stops it visits and mark them as visited to avoid reprocessing. We'll then repeat this process for each newly reached stop until we reach the target stop or exhaust all possibilities. This ensures that we find the minimum number of bus transfers needed to reach the target.
Step-by-step Algorithm
-
Initialization:
- Create a map
stopToBuses
where the key is a bus stop and the value is a list of buses that visit this stop. - Initialize an empty queue for BFS,
queue
, which will store pairs of (current_stop, buses_taken). - Initialize a set
visitedStops
to keep track of bus stops that have been visited. - Initialize a set
usedBuses
to keep track of buses that have been used.
- Create a map
-
Building the
stopToBuses
Map:- For each bus route in
routes
, and for each stop in that route, add the bus index to the list of buses in thestopToBuses
map for that stop.
- For each bus route in
-
Start BFS:
- Enqueue the
source
stop with 0 buses taken (queue.offer(new int[]{source, 0})
). - Mark the
source
stop as visited (visitedStops.add(source)
).
- Enqueue the
-
Processing the Queue:
- While the queue is not empty:
- Dequeue the front element from the queue to get the current stop and the number of buses taken so far.
- For each bus that visits the current stop:
- If the bus has already been used, skip it.
- Mark the bus as used (
usedBuses.add(bus)
). - For each stop that this bus visits:
- If this stop is the
target
, return the number of buses taken plus one. - If this stop has not been visited yet, mark it as visited and enqueue it with the number of buses taken plus one.
- If this stop is the
- While the queue is not empty:
-
If Target Not Reached:
- If the queue is empty and the target has not been reached, return -1.
Algorithm Walkthrough
Input:
- routes:
[[2, 3, 4], [5, 6, 7, 8], [4, 5, 9, 10], [10, 12]]
- source:
3
- target:
12
-
Initialization:
stopToBuses
map:{}
initially.queue
:[]
visitedStops
:{}
usedBuses
:{}
-
Building the
stopToBuses
Map:- Final
stopToBuses
map:{2: [0], 3: [0], 4: [0, 2], 5: [1, 2], 6: [1], 7: [1], 8: [1], 9: [2], 10: [2, 3], 12: [3]}
- Final
-
Start BFS:
- Enqueue (3, 0):
queue = [(3, 0)]
- Mark 3 as visited:
visitedStops = {3}
- Enqueue (3, 0):
-
Processing the Queue:
- Dequeue (3, 0):
current_stop = 3
,buses_taken = 0
- Buses visiting stop 3:
[0]
- Bus 0:
- Stops visited by bus 0:
[2, 3, 4]
- Stop 2:
- Not the target, mark visited and enqueue:
queue = [(2, 1)]
,visitedStops = {2, 3}
- Not the target, mark visited and enqueue:
- Stop 3:
- Already visited, skip.
- Stop 4:
- Not the target, mark visited and enqueue:
queue = [(2, 1), (4, 1)]
,visitedStops = {2, 3, 4}
- Not the target, mark visited and enqueue:
- Stops visited by bus 0:
- Bus 0:
- Buses visiting stop 3:
- Dequeue (2, 1):
current_stop = 2
,buses_taken = 1
- Buses visiting stop 2:
[0]
(already used, skip)
- Buses visiting stop 2:
- Dequeue (4, 1):
current_stop = 4
,buses_taken = 1
- Buses visiting stop 4:
[0, 2]
- Bus 0:
- Already used, skip.
- Bus 2:
- Stops visited by bus 2:
[4, 5, 9, 10]
- Stop 4:
- Already visited, skip.
- Stop 5:
- Not the target, mark visited and enqueue:
queue = [(5, 2)]
,visitedStops = {2, 3, 4, 5}
- Not the target, mark visited and enqueue:
- Stop 9:
- Not the target, mark visited and enqueue:
queue = [(5, 2), (9, 2)]
,visitedStops = {2, 3, 4, 5, 9}
- Not the target, mark visited and enqueue:
- Stop 10:
- Not the target, mark visited and enqueue:
queue = [(5, 2), (9, 2), (10, 2)]
,visitedStops = {2, 3, 4, 5, 9, 10}
- Not the target, mark visited and enqueue:
- Stops visited by bus 2:
- Bus 0:
- Buses visiting stop 4:
- Dequeue (5, 2):
current_stop = 5
,buses_taken = 2
- Buses visiting stop 5:
[1, 2]
- Bus 1:
- Stops visited by bus 1:
[5, 6, 7, 8]
- Stop 5:
- Already visited, skip.
- Stop 6:
- Not the target, mark visited and enqueue:
queue = [(9, 2), (10, 2), (6, 3)]
,visitedStops = {2, 3, 4, 5, 6, 9, 10}
- Not the target, mark visited and enqueue:
- Stop 7:
- Not the target, mark visited and enqueue:
queue = [(9, 2), (10, 2), (6, 3), (7, 3)]
,visitedStops = {2, 3, 4, 5, 6, 7, 9, 10}
- Not the target, mark visited and enqueue:
- Stop 8:
- Not the target, mark visited and enqueue:
queue = [(9, 2), (10, 2), (6, 3), (7, 3), (8, 3)]
,visitedStops = {2, 3, 4, 5, 6, 7, 8, 9, 10}
- Not the target, mark visited and enqueue:
- Stops visited by bus 1:
- Bus 2:
- Already used, skip.
- Bus 1:
- Buses visiting stop 5:
- Dequeue (9, 2):
current_stop = 9
,buses_taken = 2
- Buses visiting stop 9:
[2]
(already used, skip)
- Buses visiting stop 9:
- Dequeue (10, 2):
current_stop = 10
,buses_taken = 2
- Buses visiting stop 10:
[2, 3]
- Bus 2:
- Already used, skip.
- Bus 3:
- Stops visited by bus 3:
[10, 12]
- Stop 10:
- Already visited, skip.
- Stop 12:
- Target reached, return
buses_taken + 1 = 3
.
- Target reached, return
- Stops visited by bus 3:
- Bus 2:
- Buses visiting stop 10:
- Dequeue (3, 0):
-
Result:
- The minimum number of buses needed is
3
.
- The minimum number of buses needed is
Code
Complexity Analysis
Time Complexity
- Constructing the
stopToBuses
map requires iterating over each route and each stop within the route, which takes O(M \times K) time, where (M) is the number of routes and (K) is the average number of stops per route. - During the BFS, each bus route and each stop will be processed. For each route in the queue, we iterate over its stops, and for each stop, we iterate over the connected routes in the map
stopToBuses
. This takes O(M \times K \times M) time, resulting in a total time complexity of O(M^2 \times K).
Space Complexity
- The
stopToBuses
map requires O(M \times K) space to store all bus stops and their corresponding routes. - The BFS queue can store up to O(M \times K) elements in the worst case.
- The
visitedStops
andusedBuses
sets will store up to O(M \times K) elements. - Thus, the total space complexity is O(M \times K).
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible