You are given a list of bus routes, where each route is represented as a list of bus stops. All the bus routes are circular, meaning if a route contains stops [a, b, c, d], then after d the bus returns to a and repeats the cycle.
You are also given two bus stops: source and target. Your task is to determine the minimum number of buses you must take to travel from source to target. You can change buses only at bus stops that are common to two or more routes. If it is not possible to reach the target from the source, return -1.
Constraints:
At first glance, this problem looks similar to finding the shortest path in a graph. Each bus stop can be thought of as a node, and each bus route as a group of nodes connected together. However, since you can only change buses at stops shared by two or more routes, the real question is: "What's the minimum number of bus routes needed to reach the target, switching only at shared stops?"
A brute-force approach would be to simulate every possible path from the source to the target, but with up to 105 stops, this is far too slow. Instead, we need to model the problem as a graph where each node is a bus route, and there is an edge between two routes if they share a stop. The goal is to find the shortest path (fewest hops) from any route containing source to any route containing target.
This is a classic Breadth-First Search (BFS) problem, where each level of BFS represents taking another bus.
Let's break down the steps to solve the problem efficiently:
source (starting routes).target (ending routes).source == target, no buses are needed; return 0.This approach leverages a hash map for quick lookups and BFS for optimal path finding.
Example:
routes = [[1, 2, 7], [3, 6, 7]]
source = 1
target = 6
Brute-force approach:
Trying all possible paths would be exponential in the number of stops and routes, which is infeasible for large inputs.
Optimized BFS approach:
These are acceptable given the problem constraints.
from collections import defaultdict, deque
class Solution:
def numBusesToDestination(self, routes, source, target):
if source == target:
return 0
stop_to_routes = defaultdict(set)
for i, route in enumerate(routes):
for stop in route:
stop_to_routes[stop].add(i)
visited_routes = set()
visited_stops = set([source])
queue = deque()
# Start with all routes passing through source
for route in stop_to_routes[source]:
queue.append((route, 1))
visited_routes.add(route)
while queue:
route, buses = queue.popleft()
for stop in routes[route]:
if stop == target:
return buses
if stop in visited_stops:
continue
visited_stops.add(stop)
for next_route in stop_to_routes[stop]:
if next_route not in visited_routes:
visited_routes.add(next_route)
queue.append((next_route, buses + 1))
return -1
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
if (source == target) return 0;
unordered_map<int, vector<int>> stop_to_routes;
for (int i = 0; i < routes.size(); ++i) {
for (int stop : routes[i]) {
stop_to_routes[stop].push_back(i);
}
}
unordered_set<int> visited_routes;
unordered_set<int> visited_stops;
queue<pair<int, int>> q;
for (int route : stop_to_routes[source]) {
q.push({route, 1});
visited_routes.insert(route);
}
visited_stops.insert(source);
while (!q.empty()) {
auto [route, buses] = q.front(); q.pop();
for (int stop : routes[route]) {
if (stop == target) return buses;
if (visited_stops.count(stop)) continue;
visited_stops.insert(stop);
for (int next_route : stop_to_routes[stop]) {
if (!visited_routes.count(next_route)) {
visited_routes.insert(next_route);
q.push({next_route, buses + 1});
}
}
}
}
return -1;
}
};
import java.util.*;
class Solution {
public int numBusesToDestination(int[][] routes, int source, int target) {
if (source == target) return 0;
Map<Integer, List<Integer>> stopToRoutes = new HashMap<>();
for (int i = 0; i < routes.length; i++) {
for (int stop : routes[i]) {
stopToRoutes.computeIfAbsent(stop, x -> new ArrayList<>()).add(i);
}
}
Set<Integer> visitedRoutes = new HashSet<>();
Set<Integer> visitedStops = new HashSet<>();
Queue<int[]> queue = new LinkedList<>();
for (int route : stopToRoutes.getOrDefault(source, new ArrayList<>())) {
queue.offer(new int[]{route, 1});
visitedRoutes.add(route);
}
visitedStops.add(source);
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int route = curr[0], buses = curr[1];
for (int stop : routes[route]) {
if (stop == target) return buses;
if (visitedStops.contains(stop)) continue;
visitedStops.add(stop);
for (int nextRoute : stopToRoutes.getOrDefault(stop, new ArrayList<>())) {
if (!visitedRoutes.contains(nextRoute)) {
visitedRoutes.add(nextRoute);
queue.offer(new int[]{nextRoute, buses + 1});
}
}
}
}
return -1;
}
}
/**
* @param {number[][]} routes
* @param {number} source
* @param {number} target
* @return {number}
*/
var numBusesToDestination = function(routes, source, target) {
if (source === target) return 0;
const stopToRoutes = new Map();
for (let i = 0; i < routes.length; i++) {
for (const stop of routes[i]) {
if (!stopToRoutes.has(stop)) stopToRoutes.set(stop, []);
stopToRoutes.get(stop).push(i);
}
}
const visitedRoutes = new Set();
const visitedStops = new Set([source]);
const queue = [];
if (!stopToRoutes.has(source)) return -1;
for (const route of stopToRoutes.get(source)) {
queue.push([route, 1]);
visitedRoutes.add(route);
}
while (queue.length > 0) {
const [route, buses] = queue.shift();
for (const stop of routes[route]) {
if (stop === target) return buses;
if (visitedStops.has(stop)) continue;
visitedStops.add(stop);
for (const nextRoute of stopToRoutes.get(stop)) {
if (!visitedRoutes.has(nextRoute)) {
visitedRoutes.add(nextRoute);
queue.push([nextRoute, buses + 1]);
}
}
}
}
return -1;
};
The "Bus Routes" problem is a shortest-path challenge on a graph where each node is a bus route and edges represent shared stops. By mapping stops to routes and applying Breadth-First Search, we efficiently find the minimum number of buses needed to go from the source to the target. The key insight is to treat routes as nodes and use BFS to explore possible transfers, ensuring optimal performance even with large input sizes.