Bus Routes
Problem Statement
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 the0thbus 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
Try here before watching the video.
Video Explanation
Java Code
import java.util.*;
class Solution {
public int numBusesToDestination(int[][] routes, int source, int target) {
Map<Integer, List<Integer>> stopToBusMap = new HashMap<>();
Set<Integer> stopVisited = new HashSet<>();
Set<Integer> busVisited = new HashSet<>();
for(int bus = 0; bus < routes.length; bus++) {
for(int stop : routes[bus]) {
if(!stopToBusMap.containsKey(stop)) {
stopToBusMap.put(stop, new ArrayList<>());
}
stopToBusMap.get(stop).add(bus);
}
}
if(source == target) return 0;
if(!stopToBusMap.containsKey(source)) return -1;
Queue<Integer> queue = new LinkedList<>();
queue.add(source);
stopVisited.add(source);
int busesTaken = 0;
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
int currStop = queue.poll();
if(currStop == target) return busesTaken;
List<Integer> busList = stopToBusMap.get(currStop);
for(int bus : busList) {
if(!busVisited.contains(bus)) {
for(int stop : routes[bus]) {
if(!stopVisited.contains(stop)) {
queue.add(stop);
stopVisited.add(stop);
}
}
busVisited.add(bus);
}
}
}
busesTaken += 1;
}
return -1;
}
}
C++ Code
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
unordered_map<int, vector<int>> stopToBusMap;
unordered_set<int> stopVisited;
unordered_set<int> busVisited;
for (int bus = 0; bus < routes.size(); ++bus) {
for (int stop : routes[bus]) {
stopToBusMap[stop].push_back(bus);
}
}
if (source == target) {
return 0;
}
if (stopToBusMap.find(source) == stopToBusMap.end()) {
return -1;
}
queue<int> q;
q.push(source);
stopVisited.insert(source);
int busesTaken = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
int currStop = q.front();
q.pop();
if (currStop == target) {
return busesTaken;
}
vector<int>& busList = stopToBusMap[currStop];
for (int bus : busList) {
if (busVisited.find(bus) == busVisited.end()) {
for (int stop : routes[bus]) {
if (stopVisited.find(stop) == stopVisited.end()) {
q.push(stop);
stopVisited.insert(stop);
}
}
busVisited.insert(bus);
}
}
}
busesTaken += 1;
}
return -1;
}
};
Python Code
from collections import deque, defaultdict
from typing import List
class Solution:
def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
stop_to_bus_map = defaultdict(list)
stop_visited = set()
bus_visited = set()
for bus, stops in enumerate(routes):
for stop in stops:
stop_to_bus_map[stop].append(bus)
if source == target:
return 0
if source not in stop_to_bus_map:
return -1
queue = deque([source])
stop_visited.add(source)
buses_taken = 0
while queue:
size = len(queue)
for _ in range(size):
curr_stop = queue.popleft()
if curr_stop == target:
return buses_taken
bus_list = stop_to_bus_map[curr_stop]
for bus in bus_list:
if bus not in bus_visited:
for stop in routes[bus]:
if stop not in stop_visited:
queue.append(stop)
stop_visited.add(stop)
bus_visited.add(bus)
buses_taken += 1
return -1
Javascript Code
var numBusesToDestination = function(routes, source, target) {
if (source === target) {
return 0;
}
let stopToBusMap = new Map();
let stopVisited = new Set();
let busVisited = new Set();
for (let bus = 0; bus < routes.length; ++bus) {
for (let stop of routes[bus]) {
if (!stopToBusMap.has(stop)) {
stopToBusMap.set(stop, []);
}
stopToBusMap.get(stop).push(bus);
}
}
if (!stopToBusMap.has(source)) {
return -1;
}
let q = [source];
stopVisited.add(source);
let busesTaken = 0;
while (q.length > 0) {
let size = q.length;
for (let i = 0; i < size; ++i) {
let currStop = q.shift();
if (currStop === target) {
return busesTaken;
}
let busList = stopToBusMap.get(currStop);
for (let bus of busList) {
if (!busVisited.has(bus)) {
for (let stop of routes[bus]) {
if (!stopVisited.has(stop)) {
q.push(stop);
stopVisited.add(stop);
}
}
busVisited.add(bus);
}
}
}
busesTaken += 1;
}
return -1;
};
Go Code
func numBusesToDestination(routes [][]int, source int, target int) int {
if source == target {
return 0
}
stopToBusMap := make(map[int][]int)
stopVisited := make(map[int]bool)
busVisited := make(map[int]bool)
for bus, stops := range routes {
for _, stop := range stops {
stopToBusMap[stop] = append(stopToBusMap[stop], bus)
}
}
if _, exists := stopToBusMap[source]; !exists {
return -1
}
q := []int{source}
stopVisited[source] = true
busesTaken := 0
for len(q) > 0 {
size := len(q)
for i := 0; i < size; i++ {
currStop := q[0]
q = q[1:]
if currStop == target {
return busesTaken
}
busList := stopToBusMap[currStop]
for _, bus := range busList {
if _, visited := busVisited[bus]; !visited {
for _, stop := range routes[bus] {
if _, visitedStop := stopVisited[stop]; !visitedStop {
q = append(q, stop)
stopVisited[stop] = true
}
}
busVisited[bus] = true
}
}
}
busesTaken++
}
return -1
}
Complexity Analysis
Time Complexity: O(m * n), where m is the average number of stops in each route array. And n is the number of total routes. This is because of the following reasons:
- Firstly, we're building a map of stops to buses which will take O(m * n) time.
- Secondly, the queue can hold all the stops in worst case scenario and we are not visiting any stop twice, for each stop, we are looking for buses and iterating over them but we won't visit any bus twice, so if you break it down and look closely, we are visiting all the buses and stops only once. Hence, O(m * n).
Space Complexity: O(m * n), because we're building a map of stops to buses that will take O(m * n) space.