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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

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 the source stop. A hash set vis 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); hence ans 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 return ans which represents the number of buses taken until now.
  - Otherwise, add all connected routes to the queue that have not already been visited.
- After processing all routes in the current BFS level, increment ans, symbolizing a transition to the next level—which represents taking another bus.
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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example 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

Not Sure What to Study? Take the 2-min Quiz：

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 in O(R*S) time complexity, where R is the number of routes and S 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 run O(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 constant K. So this part is more accurately represented as O(S*K^2), where K 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, where V is the number of vertices (bus routes) and E 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 requires O(R*S) space.
The d dictionary: This contains at most S keys (each stop) and, for each key, a list of routes that pass by that stop. So, this contributes an additional O(S*K) space complexity where K 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 most S*K^2 but could be less if not all buses are fully connected. Thus, this adds O(V+E) space.
The vis set and q deque: These could contain each route once, resulting in O(R) space for vis and O(R) for q 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

815. Bus Routes

Problem Description

Intuition

Solution Approach

Algorithms and Data Structures Used:

Implementation Steps:

Example Walkthrough

Preprocessing Routes

Mapping Stops to Routes

Building the Graph

Initial BFS Setup