815. Bus Routes
Problem Description
In this problem, we are presented with public transportation system where buses travel on predefined circular routes indefinitely. Each bus route is described as an array where the elements represent the sequence of stops that the bus will make.
Imagine we have multiple buses, each following its own unique circular route. Each route is represented as a list of stops. For example, if we have routes[0] = [1, 5, 7]
, this means that the first bus (indexed at 0) continuously travels from stop 1 to 5, then to stop 7, and then returns back to stop 1 to repeat the cycle. Note that a single bus stop could be served by multiple bus routes.
Your task is to determine the minimum number of buses a person must take to travel from a specific bus stop source
to a specific bus stop target
. You are initially not on any bus, and can only travel between bus stops via the buses. The function should return the minimum number of buses one needs to take, or -1
if there is no possible way to get from source
to target
using the provided bus routes.
Flowchart Walkthrough
Let's analyze LeetCode 815, "Bus Routes," using the Flowchart. We'll go through each step to determine the appropriate algorithm:
Is it a graph?
- Yes: Routes can be seen as nodes, where there exists an edge between two routes if they share a common bus stop.
Is it a tree?
- No: The graph potentially forms multiple connections between nodes (i.e., routes), with routes intersecting at various bus stops.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem is essentially about finding the shortest path to traverse through various routes, not particularly about acyclicity or directedness.
Is the problem related to shortest paths?
- Yes: We seek the minimum number of bus swaps to reach a target stop from a starting stop, analogous to finding the shortest path in a graph perspective.
Is the graph weighted?
- No: Each edge (or swap between buses) can be considered as having an equal weight of one hop.
Conclusion: The flowchart supports the use of BFS since we are looking at an unweighted shortest path problem. In this case, BFS is apt for finding the shortest path in an unweighted graph, making it ideal for calculating the minimum number of bus swaps needed from one stop to another.
Intuition
To solve the bus routes problem, we can think of each bus route as a node in a graph, where edges connect nodes if the buses share a common bus stop. The problem then reduces to finding the shortest path in this graph from the node representing the bus we can take at our source to the node representing the bus that passes through our target.
Here's the step-by-step strategy behind the solution:
-
First, we simplify the representation of routes by converting each bus route list into a set for faster look-up times. This is because we'll often need to check if a certain bus route contains a specific stop.
-
The second step is to create a mapping that tells us which bus routes pass through each bus stop. This is done using a dictionary where each key is a bus stop, and the value is a list of bus routes that pass through that stop.
-
Next, a graph is created where each node represents a bus route, and edges only exist between nodes (routes) that have at least one bus stop in common.
-
The fourth step involves a breadth-first search (BFS) on the graph. BFS is chosen because it explores all routes from the current bus stop before moving to routes that are two stops away, thereby ensuring that the minimum number of buses is taken.
-
We start the BFS with all bus routes that pass through the
source
stop, tracking visited routes. If the target stop is in any currently visited route, we return the number of buses (depth of the BFS). -
If the target is not reached directly, we then expand to neighboring routes (routes sharing at least one common stop) in the BFS, again checking if the target is there at each step.
-
The BFS continues until we either find the target or exhaust all possibilities.
If the target
is found, we return the current depth of the BFS (i.e., the number of buses we've virtually 'taken'). If we've gone through the entire graph (explored all connected routes) without finding the target
, we return -1
, indicating that the journey is not possible with the given bus routes.
Learn more about Breadth-First Search patterns.
Solution Approach
The solution provided leverages several computing concepts, including graph theory, hash sets, hash maps (a.k.a dictionaries in Python), breadth-first search (BFS), and queues.
Algorithms and Data Structures Used:
-
Graph Theory: The solution treats the bus routes as nodes in a graph and the common stops between them as edges, abstracting the problem into finding the shortest path in a graph.
-
Hash Set: Each bus route is converted into a set for constant-time lookup to determine whether a route contains a particular stop.
-
Hash Map / Dictionary: Two dictionaries are utilized: one for mapping each stop to the list of routes passing through it, and another for representing the adjacency list of the route graph.
-
Breadth-First Search (BFS): BFS is used to traverse the graph levels, keeping track of the number of 'hops' or bus changes required to reach the destination.
-
Queue: A queue is pivotal for implementing BFS. The Python collection
deque
is used for its efficient append and popleft operations.
Implementation Steps:
-
Preprocessing Routes: The routes list is converted into a list of sets
s
for O(1) access to check if a target is in a particular route. -
Mapping Stops to Routes: A dictionary
d
is created where each key is a stop and each value is a list of routes passing through that stop. -
Building the Graph: Another dictionary
g
represents the graph, which is essentially an adjacency list. Two routes are connected in this graph if they have at least one common stop. -
Initial BFS Setup: A queue
q
is initiated with all the routes that have thesource
stop. A hash setvis
is also defined to record visited routes to prevent processing the same route multiple times. -
BFS Execution:
- The BFS loop begins with an assumption that we have taken one bus (since we are starting at the
source
); henceans
is initialized to 1. - It processes nodes in the current BFS level by popping from the left of the queue. For each route at the current BFS level:
- If the
target
is inside the current route's set, we returnans
which represents the number of buses taken until now. - Otherwise, add all connected routes to the queue that have not already been visited.
- If the
- After processing all routes in the current BFS level, increment
ans
, symbolizing a transition to the next level—which represents taking another bus.
- The BFS loop begins with an assumption that we have taken one bus (since we are starting at the
-
Return Result: If the BFS loop completes without returning, then there is no route to the
target
, and-1
is returned.
The implementation effectively finds the minimum number of bus changes required to go from source
to target
in a graph that represents the shared stops between bus routes.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have the following bus routes and we want to get from source
stop 2 to target
stop 9.
1routes = [[1, 2, 4], [3, 6, 9], [2, 7, 8]] 2source = 2 3target = 9
Preprocessing Routes
First, convert each route to a set for quick look-ups:
1s = [{1, 2, 4}, {3, 6, 9}, {2, 7, 8}]
Mapping Stops to Routes
Create a dictionary mapping each stop to the routes passing through:
1d = { 2 1: [0], 3 2: [0, 2], 4 3: [1], 5 4: [0], 6 6: [1], 7 7: [2], 8 8: [2], 9 9: [1] 10}
Building the Graph
Create a graph where nodes are connected if they share common stops:
1g = { 2 0: [2], 3 1: [], 4 2: [0] 5}
Here, routes 0 and 2 are connected because they both serve stop 2.
Initial BFS Setup
Initialize the BFS queue with routes that have the source
stop, and a visited set:
1q = deque([0, 2]) 2vis = set()
BFS Execution
Start BFS traversal. We take route 0 or route 2 first (starting at level 1). For each route in the queue:
- Check if
target
stop 9 is in the set of the current route. - If not, look for connected routes that have not been visited and add them to the queue.
- Keep track of visited routes to prevent revisiting:
1ans = 1
2while q:
3 for _ in range(len(q)):
4 route = q.popleft()
5 if 9 in s[route]:
6 return ans # Stop is found; return 1 since we took 1 bus.
7 vis.add(route)
8 for connected_route in g[route]:
9 if connected_route not in vis:
10 q.append(connected_route)
11 ans += 1
Since the target
is not in route 0 or route 2, we check connected routes, but neither adds more connections, so ans
increments to 2.
Return Result
Upon subsequent iterations, we find that the target
stop 9 is part of route 1. Therefore, at the BFS stage where ans
is 2, we find our target
within route 1, which is connected to route 0, so we can take route 0 then switch to route 1. Thus, we need to take at least 2 buses to reach our target. If we don't find the target, we would return -1
.
This completes our example, demonstrating that it is possible to reach stop 9 from stop 2 by taking 2 buses, with the route sequence being [2, 4, 6, 9]
considered from the bus routes.
Solution Implementation
1from collections import deque, defaultdict
2
3class Solution:
4 def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
5 # If the source and target are the same, no bus needs to be taken.
6 if source == target:
7 return 0
8
9 # Convert each route to a set for faster checks later on.
10 sets_of_routes = [set(route) for route in routes]
11
12 # Create a dictionary where each stop maps to a list of buses (routes) that visit that stop.
13 stop_to_buses_dict = defaultdict(list)
14 for i, route in enumerate(routes):
15 for stop in route:
16 stop_to_buses_dict[stop].append(i)
17
18 # Build a graph where each node represents a bus and edges connect buses that share a common stop.
19 bus_graph = defaultdict(list)
20 for buses in stop_to_buses_dict.values():
21 num_buses = len(buses)
22 for i in range(num_buses):
23 for j in range(i + 1, num_buses):
24 first, second = buses[i], buses[j]
25 bus_graph[first].append(second)
26 bus_graph[second].append(first)
27
28 # Start BFS from the buses that can be taken from the source stop.
29 queue = deque(stop_to_buses_dict[source])
30 number_of_buses = 1
31 visited_buses = set(stop_to_buses_dict[source])
32
33 while queue:
34 # Process all nodes on the current level.
35 for _ in range(len(queue)):
36 current_bus = queue.popleft()
37
38 # If the target stop is in the current bus's route, return the number of buses needed.
39 if target in sets_of_routes[current_bus]:
40 return number_of_buses
41
42 # Check unvisited buses that can be reached from the current bus.
43 for adjacent_bus in bus_graph[current_bus]:
44 if adjacent_bus not in visited_buses:
45 visited_buses.add(adjacent_bus)
46 queue.append(adjacent_bus)
47
48 # Increment the number of buses needed as we are now moving to the next level in BFS.
49 number_of_buses += 1
50
51 # If no path is found, return -1 to signify that destination cannot be reached.
52 return -1
53
1class Solution {
2 public int numBusesToDestination(int[][] routes, int source, int target) {
3 // If the source and target are the same, no need to take any buses.
4 if (source == target) {
5 return 0;
6 }
7
8 int numRoutes = routes.length;
9 // Create a set to store the stops of each route.
10 Set<Integer>[] stopsPerRouteSet = new Set[numRoutes];
11 // Create a graph to represent the connections between routes.
12 List<Integer>[] routeGraph = new List[numRoutes];
13 // Initialize the sets and lists.
14 Arrays.setAll(stopsPerRouteSet, k -> new HashSet<>());
15 Arrays.setAll(routeGraph, k -> new ArrayList<>());
16 // Map to store the routes that pass through each stop.
17 Map<Integer, List<Integer>> stopToRoutesMap = new HashMap<>();
18
19 // Build the stop sets and the stop to routes map.
20 for (int i = 0; i < numRoutes; ++i) {
21 for (int stop : routes[i]) {
22 stopsPerRouteSet[i].add(stop);
23 stopToRoutesMap.computeIfAbsent(stop, k -> new ArrayList<>()).add(i);
24 }
25 }
26
27 // Build the route graph based on shared stops.
28 for (var routesSharingStop : stopToRoutesMap.values()) {
29 int numConnectedRoutes = routesSharingStop.size();
30 for (int i = 0; i < numConnectedRoutes; ++i) {
31 for (int j = i + 1; j < numConnectedRoutes; ++j) {
32 int routeA = routesSharingStop.get(i), routeB = routesSharingStop.get(j);
33 routeGraph[routeA].add(routeB);
34 routeGraph[routeB].add(routeA);
35 }
36 }
37 }
38
39 // Queue for BFS traversal of the route graph.
40 Deque<Integer> queue = new ArrayDeque<>();
41 // Set to keep track of visited routes.
42 Set<Integer> visitedRoutes = new HashSet<>();
43 // Start the BFS traversal from routes passing through the source stop.
44 for (int route : stopToRoutesMap.getOrDefault(source, new ArrayList<>())) {
45 queue.offer(route);
46 visitedRoutes.add(route);
47 }
48
49 // Number of buses needed.
50 int busesNeeded = 1;
51
52 // Perform BFS to find the fewest number of buses we must take to travel from source to target.
53 while (!queue.isEmpty()) {
54 for (int k = queue.size(); k > 0; --k) {
55 int currentRoute = queue.pollFirst();
56 // If the route reaches the target stop, return the number of buses needed.
57 if (stopsPerRouteSet[currentRoute].contains(target)) {
58 return busesNeeded;
59 }
60 // Add neighboring routes to the queue if they haven't been visited.
61 for (int neighbor : routeGraph[currentRoute]) {
62 if (!visitedRoutes.contains(neighbor)) {
63 visitedRoutes.add(neighbor);
64 queue.offer(neighbor);
65 }
66 }
67 }
68 // Increment the buses needed after each level of BFS.
69 ++busesNeeded;
70 }
71
72 // If we can't reach the target, return -1.
73 return -1;
74 }
75}
76
1#include <vector>
2#include <unordered_set>
3#include <unordered_map>
4#include <queue>
5using namespace std;
6
7class Solution {
8public:
9 // This function computes the minimum number of buses we must take to go from source
10 // to the target bus stop. Each bus route is represented as a list of bus stops it goes through.
11 // source - the bus stop from where we start
12 // target - the bus stop where we want to reach
13 int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
14 // If the source and target are the same, no need to take any bus
15 if (source == target) {
16 return 0;
17 }
18
19 // Initialize the necessary data structures
20 int totalRoutes = routes.size();
21
22 // Convert the list of routes to sets for faster access
23 vector<unordered_set<int>> stopsForRoute(totalRoutes);
24 // Graph representation of the bus routes. Each node is a bus route.
25 vector<vector<int>> graph(totalRoutes);
26 // Dictionary to map each stop to a list of routes that contain that stop
27 unordered_map<int, vector<int>> stopToRoutesMap;
28
29 for (int i = 0; i < totalRoutes; ++i) {
30 for (int stop : routes[i]) {
31 stopsForRoute[i].insert(stop);
32 stopToRoutesMap[stop].push_back(i);
33 }
34 }
35
36 // Create edges between routes that share common bus stops
37 for (auto& kv : stopToRoutesMap) {
38 auto& routesUsingStop = kv.second; // routes that use 'stop'
39 for (size_t i = 0; i < routesUsingStop.size(); ++i) {
40 for (size_t j = i + 1; j < routesUsingStop.size(); ++j) {
41 int routeA = routesUsingStop[i];
42 int routeB = routesUsingStop[j];
43 graph[routeA].push_back(routeB);
44 graph[routeB].push_back(routeA);
45 }
46 }
47 }
48
49 // Initialize the BFS
50 queue<int> toVisit; // queue for BFS
51 unordered_set<int> visitedRoutes; // holds visited routes to avoid loops
52 int busesTaken = 1;
53
54 // Add the starting routes to the queue, those that contain the 'source'
55 for (int route : stopToRoutesMap[source]) {
56 toVisit.push(route);
57 visitedRoutes.insert(route);
58 }
59
60 // Perform BFS
61 while (!toVisit.empty()) {
62 int currentLevelSize = toVisit.size();
63 for (int i = 0; i < currentLevelSize; ++i) {
64 int currentRoute = toVisit.front();
65 toVisit.pop();
66
67 // Check if the target stop is on the current route
68 if (stopsForRoute[currentRoute].count(target)) {
69 return busesTaken;
70 }
71
72 // Add all unvisited connecting routes to the queue
73 for (int neighbourRoute : graph[currentRoute]) {
74 if (!visitedRoutes.count(neighbourRoute)) {
75 visitedRoutes.insert(neighbourRoute);
76 toVisit.push(neighbourRoute);
77 }
78 }
79 }
80 busesTaken++; // Move to the next level which equals taking another bus
81 }
82
83 // If the target is unreachable, return -1
84 return -1;
85 }
86};
87
1// Import necessary data structures from 'collections.ts' module
2import { Queue } from 'collections.ts';
3
4// This function computes the minimum number of buses we must take to go from a source
5// to a target bus stop. Each bus route is represented as an array of bus stops it goes through.
6/**
7 *
8 * @param routes - array representing bus routes, where each route is an array of bus stops.
9 * @param source - the bus stop from where we start.
10 * @param target - the bus stop where we want to reach.
11 * @returns the minimum number of buses required to travel from source to target, or -1 if unreachable.
12 */
13function numBusesToDestination(routes: number[][], source: number, target: number): number {
14 // If the source and target are the same, no need to take any bus
15 if (source === target) {
16 return 0;
17 }
18
19 // Initialize the necessary data structures
20 const totalRoutes: number = routes.length;
21
22 // Convert the list of routes to Sets for faster access
23 const stopsForRoute: Set<number>[] = routes.map(route => new Set(route));
24
25 // Graph representation of the bus routes. Each node is a bus route.
26 const graph: number[][] = new Array(totalRoutes).fill([]).map(() => []);
27
28 // Map each stop to a list of routes that contain that stop
29 const stopToRoutesMap: Map<number, number[]> = new Map();
30
31 // Fill the stopToRoutesMap and graph with appropriate data
32 routes.forEach((route, i) => {
33 route.forEach(stop => {
34 if (!stopToRoutesMap.has(stop)) {
35 stopToRoutesMap.set(stop, []);
36 }
37 stopToRoutesMap.get(stop)!.push(i);
38 });
39 });
40
41 // Create edges between routes that share common bus stops
42 stopToRoutesMap.forEach((routesUsingStop) => {
43 routesUsingStop.forEach((routeA, i) => {
44 routesUsingStop.slice(i + 1).forEach(routeB => {
45 graph[routeA].push(routeB);
46 graph[routeB].push(routeA);
47 });
48 });
49 });
50
51 // Initialize the BFS
52 const toVisit: Queue<number> = new Queue(); // Queue for BFS
53 const visitedRoutes: Set<number> = new Set(); // Holds visited routes to avoid loops
54 let busesTaken: number = 1;
55
56 // Add the starting routes to the queue, those that contain the 'source'
57 stopToRoutesMap.get(source)?.forEach(route => {
58 toVisit.enqueue(route);
59 visitedRoutes.add(route);
60 });
61
62 // Perform BFS
63 while (!toVisit.isEmpty()) {
64 let currentLevelSize: number = toVisit.length;
65 for (let i = 0; i < currentLevelSize; ++i) {
66 const currentRoute: number = toVisit.dequeue()!;
67
68 // Check if the target stop is on the current route
69 if (stopsForRoute[currentRoute].has(target)) {
70 return busesTaken;
71 }
72
73 // Add all unvisited connecting routes to the queue
74 graph[currentRoute].forEach(neighbourRoute => {
75 if (!visitedRoutes.has(neighbourRoute)) {
76 visitedRoutes.add(neighbourRoute);
77 toVisit.enqueue(neighbourRoute);
78 }
79 });
80 }
81 busesTaken++; // Move to the next level which equals taking another bus
82 }
83
84 // If the target is unreachable, return -1
85 return -1;
86}
87
Time and Space Complexity
Time Complexity
The time complexity of the code is composed of three main parts:
- Constructing the
s
list: This loops over each route and each stop within that route, which results inO(R*S)
time complexity, whereR
is the number of routes andS
is the average number of stops per route. - Building the graph
g
: This involves nested loops over each stop's routes. In the worst case, if every stop is on every route, the inner loop could runO(R^2)
times for each stop. However, this is not very likely in a real-world scenario. Generally, the number of buses a stop connects to would be a smaller constantK
. So this part is more accurately represented asO(S*K^2)
, whereK
is the average number of connecting routes to any stop. - BFS traversal of the graph: In the worst case, this could visit every vertex and edge in the graph constructed in the previous step. The vertices in the graph are the bus routes, and the edges are connections between routes that share a common stop. At worst, this results in
O(V+E)
complexity, whereV
is the number of vertices (bus routes) andE
is the number of edges (connections between routes).
Hence, the overall time complexity is approximately O(R*S + S*K^2 + V+E)
.
Space Complexity
The space complexity of the code is determined by:
- The
s
list: This list stores a set of stops for each route, which requiresO(R*S)
space. - The
d
dictionary: This contains at mostS
keys (each stop) and, for each key, a list of routes that pass by that stop. So, this contributes an additionalO(S*K)
space complexity whereK
is the average number of routes per stop. - The
g
graph: The graph contains a vertex for each route, and an edge for each connection between routes that share a stop. The number of connections is at mostS*K^2
but could be less if not all buses are fully connected. Thus, this addsO(V+E)
space. - The
vis
set andq
deque: These could contain each route once, resulting inO(R)
space forvis
andO(R)
forq
at worst.
The overall space complexity is: O(R*S + S*K + V+E)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.