Log inSign up
hardLeetCodeNot Started

Bus Routes

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

You are given an array routes representing bus routes where routes[i] is a bus route that the i^{th} bus repeats forever. For example, if routes[0] = [1, 5, 7], this means that the 0^{th} bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> ... 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.

Constraints:

  • 1 <= routes.length <= 500
  • 1 <= routes[i].length <= 105
  • All values of routes[i] are unique.
  • sum(routes[i].length) <= 105
  • 0 <= routes[i][j] < 106
  • 0 <= source, target < 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate transit transfer problems as dual graphs (vehicles as vertices).
  • Map stops to vehicle IDs for O(1) transfer discovery.
  • Implement level-order BFS for minimal transfer calculation.
  • Optimize visited checks on both vehicle and stop levels to guarantee linear time.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever a transit system problem asks to minimize the number of transfers or vehicles taken (rather than stops), create a bipartite or dual graph where vehicles are nodes and common stops are edges.

1. Stop-Level BFS

Intuition

Model every bus stop as a graph vertex. Connect every pair of stops that belong to the same bus route with an edge. Run BFS from source to target. However, since a route with K stops adds O(K2) edges, dense routes lead to Time and Memory Limit Exceeded.

Algorithm

  1. If source == target, return 0.
  2. For each route, connect all pairs of stops (u, v) in an adjacency list.
  3. Run BFS from source stop.
  4. This incurs quadratic edge explosion (K2) for large routes.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5#include <queue>
6
7int numBusesToDestinationBrute(std::vector<std::vector<int>>& routes, int source, int target) {
8 if (source == target) return 0;
9
10 std::unordered_map<int, std::unordered_set<int>> adj;
11 for (const auto& route : routes) {
12 for (size_t i = 0; i < route.size(); ++i) {
13 for (size_t j = i + 1; j < route.size(); ++j) {
14 adj[route[i]].insert(route[j]);
15 adj[route[j]].insert(route[i]);
16 }
17 }
18 }
19
20 std::queue<std::pair<int, int>> q;
21 std::unordered_set<int> visited;
22 q.push({source, 0});
23 visited.insert(source);
24
25 while (!q.empty()) {
26 auto [stop, buses] = q.front();
27 q.pop();
28
29 if (stop == target) return buses;
30
31 for (int next : adj[stop]) {
32 if (!visited.count(next)) {
33 visited.insert(next);
34 q.push({next, buses + 1});
35 }
36 }
37 }
38 return -1;
39}
40
41int main() {
42 std::vector<std::vector<int>> routes = {{1, 2, 7}, {3, 6, 7}};
43 std::cout << "Buses (Brute): " << numBusesToDestinationBrute(routes, 1, 6) << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(sum(K_i^2)) which exceeds time limits when routes have 10^5 stops.
  • Space complexity: O(sum(K_i^2)) memory explosion.

2. Bus-to-Bus Adjacency Matrix BFS

Intuition

Represent each bus route as a graph node. Two bus routes i and j have an edge between them if they share at least one common stop. Build this bus-to-bus adjacency graph (N × N where N <= 500), then run BFS on the bus graph from all buses containing source to all buses containing target.

Algorithm

  1. If source == target, return 0.
  2. Build a graph of size N (number of routes). Check intersection between route sets i and j.
  3. Find all buses containing source -> enqueue with distance 1.
  4. Find all buses containing target -> targetBuses set.
  5. Run BFS on the bus graph. Return distance when any bus in targetBuses is popped.
  6. Return -1 if unreachable.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4#include <queue>
5
6int numBusesBusGraph(std::vector<std::vector<int>>& routes, int source, int target) {
7 if (source == target) return 0;
8 int n = routes.size();
9
10 std::vector<std::unordered_set<int>> routeSets(n);
11 for (int i = 0; i < n; ++i) {
12 routeSets[i] = std::unordered_set<int>(routes[i].begin(), routes[i].end());
13 }
14
15 std::vector<std::vector<int>> busAdj(n);
16 for (int i = 0; i < n; ++i) {
17 for (int j = i + 1; j < n; ++j) {
18 for (int stop : routes[i]) {
19 if (routeSets[j].count(stop)) {
20 busAdj[i].push_back(j);
21 busAdj[j].push_back(i);
22 break;
23 }
24 }
25 }
26 }
27
28 std::queue<int> q;
29 std::vector<int> dist(n, -1);
30
31 for (int i = 0; i < n; ++i) {
32 if (routeSets[i].count(source)) {
33 q.push(i);
34 dist[i] = 1;
35 }
36 }
37
38 while (!q.empty()) {
39 int u = q.front();
40 q.pop();
41
42 if (routeSets[u].count(target)) return dist[u];
43
44 for (int v : busAdj[u]) {
45 if (dist[v] == -1) {
46 dist[v] = dist[u] + 1;
47 q.push(v);
48 }
49 }
50 }
51 return -1;
52}
53
54int main() {
55 std::vector<std::vector<int>> routes = {{1, 2, 7}, {3, 6, 7}};
56 std::cout << "Buses (Bus-Graph): " << numBusesBusGraph(routes, 1, 6) << std::endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(N^2 * K) to compare all pairs of bus routes, where N is routes count and K is route length.
  • Space complexity: O(N^2) for the bus-to-bus adjacency list.

3. Optimal BFS with Stop-to-Buses Inverted Index

Intuition

Avoid the O(N2) pairwise route intersection check altogether. Build an inverted index stopToBuses[stop] = [bus_ids]. Queue stores pairs (bus_id, buses_taken). Maintain a visitedBuses array to ensure each bus route is processed at most once, and a visitedStops set to ensure no stop is re-inspected. This runs in strictly linear O(\sum |routes[i]|) time.

Algorithm

  1. If source == target, return 0.
  2. Map each stop to the list of bus indices that stop there: stopToBuses[stop].push_back(bus_id).
  3. If source or target has no buses, return -1.
  4. Initialize visitedBuses array of size N with false.
  5. Initialize visitedStops set.
  6. Initialize queue q.
  7. Enqueue all buses that visit source with distance 1: for each b in stopToBuses[source]: visitedBuses[b] = true, q.push({b, 1}).
  8. While q is not empty:
  9. Pop (bus, busesCount).
  10. For each stop in routes[bus]:
  11. If stop == target, return busesCount.
  12. If visitedStops.count(stop) continue.
  13. visitedStops.insert(stop).
  14. For each nextBus in stopToBuses[stop]:
  15. If !visitedBuses[nextBus]:
  16. visitedBuses[nextBus] = true
  17. q.push({nextBus, busesCount + 1}).
  18. Return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5#include <queue>
6
7int numBusesToDestination(std::vector<std::vector<int>>& routes, int source, int target) {
8 if (source == target) return 0;
9
10 int n = routes.size();
11 std::unordered_map<int, std::vector<int>> stopToBuses;
12 for (int i = 0; i < n; ++i) {
13 for (int stop : routes[i]) {
14 stopToBuses[stop].push_back(i);
15 }
16 }
17
18 if (!stopToBuses.count(source) || !stopToBuses.count(target)) return -1;
19
20 std::queue<std::pair<int, int>> q; // {bus_id, buses_taken}
21 std::vector<bool> visitedBuses(n, false);
22 std::unordered_set<int> visitedStops;
23
24 for (int bus : stopToBuses[source]) {
25 visitedBuses[bus] = true;
26 q.push({bus, 1});
27 }
28
29 while (!q.empty()) {
30 auto [bus, count] = q.front();
31 q.pop();
32
33 for (int stop : routes[bus]) {
34 if (stop == target) return count;
35
36 if (visitedStops.insert(stop).second) {
37 for (int nextBus : stopToBuses[stop]) {
38 if (!visitedBuses[nextBus]) {
39 visitedBuses[nextBus] = true;
40 q.push({nextBus, count + 1});
41 }
42 }
43 }
44 }
45 }
46
47 return -1;
48}
49
50int main() {
51 std::vector<std::vector<int>> routes = {{1, 2, 7}, {3, 6, 7}};
52 std::cout << "Optimal Buses (Inverted Index): " << numBusesToDestination(routes, 1, 6) << std::endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(sum(|routes[i]|)) strictly linear in the total number of stops across all routes.
  • Space complexity: O(sum(|routes[i]|)) to store the stopToBuses inverted index and visited sets.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Stop-Level BFSO(sum(K_i^2))O(sum(K_i^2))Conceptually familiar stop-to-stop mapping.Quadratic edge explosion per route; causes TLE/MLE.
2.Bus-to-Bus Graph BFSO(N^2 * K)O(N^2)Operates on N bus vertices.Pairwise bus route intersection check is slow when routes are numerous.
3.Inverted Index Stop-to-Buses BFSOptimalO(sum(|routes[i]|))O(sum(|routes[i]|))Strictly linear time; visits each stop and bus route at most once.Requires tracking visited status for both buses and stops.

Common Pitfalls & Crucial Edge Cases

Forgetting the source == target base case.

The source and target can be equal; without an initial check, the algorithm might board a bus and return 1 instead of 0.

Not tracking visited stops and re-processing busy transit hubs repeatedly.

Maintain a visitedStops set to ensure each hub stop is only expanded once.

Crucial Edge Cases to Validate:

  • source == target — Return 0 immediately without exploring any routes.
  • source or target not present in any route — Return -1 immediately.
  • Disconnected bus components (target on isolated network) — Queue empties without reaching target; returns -1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the graph transformation clearly: 'This is a shortest path problem on the dual graph of buses rather than stops.'
  2. Explain the dual visited check: visitedBuses prevents cycling between buses, visitedStops prevents re-evaluating popular transfer hubs.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why should source == target return 0 instead of 1?

2.Why is BFS on buses better than BFS on stops?

3.What is the time complexity of the optimal inverted-index BFS approach?

Back to DSA Sheet