Bus Routes
Bus Routes:
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 the 0th bus travels in the sequence 1 -> 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 <= 5001 <= routes[i].length <= 10^5- All the values of
routes[i]are unique. sum(routes[i].length) <= 10^50 <= routes[i][j] < 10^60 <= source, target < 10^6
Try this Problem on your own or check similar problems:
Solution:
- Java
- JavaScript
- Python
- C++
class Solution {
private class Graph{
Map<Integer, List<Integer>> graph;
public Graph(){
graph = new HashMap<>();
}
public void buildGraph(int[][] routes){
for(int i = 0; i < routes.length; ++i){
for(int j = 0; j < routes[i].length; ++j){
graph.computeIfAbsent(routes[i][j], k -> new ArrayList<>()).add(i);
}
}
}
private int bfs(int[][] routes, int source, int destination){
Queue<Integer> q = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
q.add(source);
int level = 1;
while(!q.isEmpty()){
int size = q.size();
while(size-->0){
int v = q.poll();
List<Integer> buses = graph.get(v);
for(int bus : buses){
if(!visited.contains(bus)){
visited.add(bus);
for(int i = 0; i < routes[bus].length; ++i){
if(routes[bus][i] == destination) return level;
q.add(routes[bus][i]);
}
}
}
}
++level;
}
return -1;
}
}
public int numBusesToDestination(int[][] routes, int source, int target) {
if(source == target) return 0;
Graph g = new Graph();
g.buildGraph(routes);
return g.bfs(routes, source, target);
}
}
/**
* @param {number[][]} routes
* @param {number} source
* @param {number} target
* @return {number}
*/
var numBusesToDestination = function (routes, source, target) {
if (source === target) return 0;
const graph = new Map();
for (let i = 0; i < routes.length; i++) {
for (const stop of routes[i]) {
if (!graph.has(stop)) {
graph.set(stop, new Set());
}
graph.get(stop).add(i);
}
}
const queue = [];
const visited = new Set();
const busesVisited = new Set();
let level = 0;
queue.push(source);
visited.add(source);
while (queue.length > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const stop = queue.shift();
if (stop === target) return level;
const buses = graph.get(stop);
for (const bus of buses) {
if (!busesVisited.has(bus)) {
for (const nextStop of routes[bus]) {
if (!visited.has(nextStop)) {
queue.push(nextStop);
visited.add(nextStop);
}
}
busesVisited.add(bus);
}
}
}
level++;
}
return -1;
};
class Solution:
def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
if source == target:
return 0
graph = defaultdict(set)
for i in range(len(routes)):
for stop in routes[i]:
graph[stop].add(i)
queue = deque()
visited = set()
buses_visited = set()
level = 0
queue.append(source)
visited.add(source)
while queue:
size = len(queue)
for _ in range(size):
stop = queue.popleft()
if stop == target:
return level
buses = graph[stop]
for bus in buses:
if bus not in buses_visited:
for next_stop in routes[bus]:
if next_stop not in visited:
queue.append(next_stop)
visited.add(next_stop)
buses_visited.add(bus)
level += 1
return -1
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
if (source == target)
return 0;
Graph g;
g.buildGraph(routes);
return g.bfs(routes, source, target);
}
private:
class Graph {
public:
std::unordered_map<int, std::vector<int>> graph;
void buildGraph(const std::vector<std::vector<int>>& routes) {
for (int i = 0; i < routes.size(); ++i) {
for (int j = 0; j < routes[i].size(); ++j) {
int stop = routes[i][j];
graph[stop].push_back(i);
}
}
}
int bfs(const std::vector<std::vector<int>>& routes, int source, int destination) {
std::queue<int> q;
std::set<int> visited;
q.push(source);
int level = 1;
while (!q.empty()) {
int size = q.size();
while (size-- > 0) {
int stop = q.front();
q.pop();
const std::vector<int>& buses = graph[stop];
for (int bus : buses) {
if (!visited.count(bus)) {
visited.insert(bus);
for (int i = 0; i < routes[bus].size(); ++i) {
int nextStop = routes[bus][i];
if (nextStop == destination)
return level;
q.push(nextStop);
}
}
}
}
++level;
}
return -1;
}
};
};
Time/Space Complexity:
- Time Complexity: O(V+E)
- Space Complexity: O(V+E)
Explanation:
The space and time complexity are proportional to the number of edges E and vertices V in created graph. It's always a good idea to model the problem as a graph if you have obvious relations between elements. And since we are searching for the shortest path in the unweighted graph, we can be sure that BFS approach will produce the minimum spanning tree visiting all the vertices in graph starting from the source. Since BFS is level-based traversal we know that the height of destination node/vertex in the spanning tree will be the shortest path from source to destination. You can think of buses as edges between stations which are vertices. Note that most of the time is spent on building the graph, if we choose to build graph by iterating over all routes, and then adding edge for each station in each route we would spend O(nr^2) where n is number of routes and r is the average route length. But we can optimize this by iterating over all stations in each bus route and adding the bus edge for each station accessible by the bus. Now in BFS we don't track the visited vertices but visited edges and for each edge/bus we can take from the current station we check if we can reach the destination, if not we add the intermediate stations and visit those. If we end our BFS search without getting to the destination, we know there doesn’t exist a path in the graph connecting source and destination and we return -1. Note that also we have far more stations, than buses, for example if you would have edge connecting each station to other station we can reach and let's say station is reachable by two bus lines than on the first level we would have to visit 2 * 10^5 edges (assuming max size route size 1 <= routes[i].length <= 10^5), but if use bus lines as edges we could only end up with 500 edges to follow.
Note that each bus route forms a connected graph (every vertex has a path to any other vertex in the graph) on its own, so constructing additional edges between those vertices would be a waste of time/space. You can think of graph as hypergraph (edges connecting node with more than one other node), so we're still traversing through all nodes and then through all of its edges like we do in regular BFS.