Problem
You are given an array routes
representing bus routes where routes[i]
is a bus route that the ith
bus repeats forever.
- For example, if
routes[0] = [1, 5, 7]
, this means that the0th
bus travels in the sequence1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...
forever.
You will start at the bus stop source
(You are not on any bus initially), and you want to go to the bus stop target
. You can travel between bus stops by buses only.
Return **the least number of buses you must take to travel from *source
* to **target
. Return -1
if it is not possible.
Example 1:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Example 2:
Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1
Constraints:
1 <= routes.length <= 500
.1 <= routes[i].length <= 105
All the values of
routes[i]
are unique.sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106
Solution
/**
* @param {number[][]} routes
* @param {number} source
* @param {number} target
* @return {number}
*/
var numBusesToDestination = function(routes, source, target) {
if (source === target) return 0;
var stopToBusMap = {};
// O(n * m)
for (var i = 0 ; i < routes.length; i++) {
for (var j = 0; j < routes[i].length; j++) {
var stop = routes[i][j];
stopToBusMap[stop] = stopToBusMap[stop] || [];
stopToBusMap[stop].push(i);
}
}
// O(n * m * n)
var busToBusMap = Array(routes.length).fill(0).map(() => []);
for (var i = 0 ; i < routes.length; i++) {
var busMap = Array(routes.length);
for (var j = 0; j < routes[i].length; j++) {
var stop = routes[i][j];
stopToBusMap[stop].forEach(bus => {
bus !== i && !busMap[bus] && busToBusMap[i].push(bus);
busMap[bus] = true;
});
}
}
if (!stopToBusMap[target] || !stopToBusMap[source]) return -1;
var targetBusMap = stopToBusMap[target].reduce((map, bus) => {
map[bus] = true;
return map;
}, {});
var visited = Array(routes.length);
var queue = stopToBusMap[source];
var res = 1;
queue.forEach(bus => visited[bus] = true);
// O(n)
while (queue.length) {
var nextQueue = [];
for (var i = 0; i < queue.length; i++) {
var bus = queue[i];
if (targetBusMap[bus]) return res;
for (var j = 0; j < busToBusMap[bus].length; j++) {
var bus2 = busToBusMap[bus][j];
if (visited[bus2]) continue;
visited[bus2] = true;
nextQueue.push(bus2);
}
}
queue = nextQueue;
res += 1;
}
return -1;
};
Explain:
nope.
Complexity:
- Time complexity : O(n ^ 2 * m).
- Space complexity : O(n * m).