Editorial
Core insight
Bus Routes · Graph Traversal Patterns (DFS & BFS)
Core Insight for Bus Routes
The key intuition for solving LeetCode 815 efficiently lies in redefining the graph structure and optimizing the search direction.
First, instead of viewing the graph as Stop -> Stop, it is more efficient to map Stop -> List of Buses. This allows us to jump from a stop to an entire route instantly.
Second, the standard BFS search space grows exponentially: , where is the branching factor and is the distance. By using Bidirectional BFS, we run two simultaneous searches: one starting from source and one from target. These two searches meet in the middle. The complexity drops roughly to . In dense graphs like bus networks, this optimization is significant.
Visual Description:
Imagine dropping a pebble into a pond at the source location and another pebble at the target location. Two circular ripples (wavefronts) begin to expand outward. The source ripple represents all stops reachable with 1 bus, then 2 buses, etc. The target ripple represents stops that can reach the destination with 1 bus, 2 buses, etc. The moment these two expanding circles touch or overlap, we have found the shortest connection. The total buses required is the sum of the expansion levels of both ripples at the collision point.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 815: Bus Routes Solution & Explanation
Problem Overview
TL;DR: We model the bus network as a graph and perform a Bidirectional Breadth-First Search (BFS) to find the minimum number of buses required to connect the source stop to the target stop.
The LeetCode 815 problem, "Bus Routes," asks us to find the minimum number of buses one must take to travel from a starting bus stop (source) to a destination bus stop (target). We are given a list of circular routes, where each route consists of a sequence of stops. If no path exists, we must return -1.
This is a classic shortest-path problem in an unweighted graph, making it a popular interview question for testing graph traversal knowledge.
Brute Force Approach for Bus Routes
A naive approach might attempt to model the system strictly by stops. One could construct a graph where every stop is a node, and an edge exists between two nodes if they are consecutive stops on a route. To handle the "cost," we would only increment the counter when switching from one route to another.
The brute force algorithm would look like this:
- Construct an adjacency matrix or list where every stop points to its neighbors.
- Perform a standard Depth-First Search (DFS) or BFS to find all paths from
sourcetotarget. - Track the number of route changes for every path and return the minimum.
Why this fails
The primary issue is the graph construction and the density of connections.
- Graph Size: A single route with stops implies that all stops are interconnected (you can reach any stop from any other stop on the same bus). Representing this as stop-to-stop edges creates a dense graph with up to edges, where is the total number of stops.
- Time Complexity: With up to total stops, an approach will result in a Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE).
- Inefficiency: DFS explores deep paths that are likely suboptimal for finding the shortest path (minimum buses), leading to redundant computations.
Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)
We will implement the Bidirectional BFS strategy with the following steps:
- Graph Mapping: Pre-process the
routesarray to build an adjacency list mapping eachstopto the list ofbus_indicesthat pass through it. - Initialization: Create two queues (
qSourceandqTarget) and two visited maps (visSourceandvisTarget).visSourcetracks stops reachable from the start, andvisTargettracks stops reachable from the end. The maps store the number of buses taken to reach that stop. - Frontier Expansion: In each step of the while loop, we expand the smaller queue (to balance the search growth).
- Traversal Logic:
- Pop a stop
ufrom the current queue. - Retrieve all buses passing through
u. - For each bus, iterate through all stops
vin that route. - Intersection Check: If stop
vhas already been visited by the opposing search, we have found a connection. The answer isdepth_from_source + depth_from_target + 1. - If
vis unvisited in the current direction, mark it as visited and add it to the current queue.
- Pop a stop
- Pruning: To prevent TLE, we must ensure we don't process the same bus route multiple times for the same direction. We can maintain a visited set for buses as well.
Execution Flow
- Edge Case Check: If
source == target, return 0 immediately. - Build Graph: Iterate through
routes. Create a mapstop_to_buseswherekey = stop_idandvalue = [list of bus_indices]. - Setup BFS:
- Initialize
q_startwithsource,vis_startmap with{source: 0}. - Initialize
q_endwithtarget,vis_endmap with{target: 0}.
- Initialize
- Loop: While both queues are non-empty:
- Select the queue with fewer elements to expand (let's say
q_start). - For each stop in the current level of
q_start:- Identify all buses serving this stop.
- For each unvisited bus in this direction:
- Iterate through all stops on this bus.
- If a stop exists in
vis_end, returnvis_start[current_stop] + vis_end[found_stop] + 1. - If the stop is not in
vis_start, add tovis_start(increment depth) andq_start. - Mark the bus as visited to avoid redundant checks.
- Select the queue with fewer elements to expand (let's say
- Termination: If queues empty without intersection, return -1.
Proof of Correctness
The algorithm is correct because BFS guarantees finding the shortest path in an unweighted graph. By expanding layer by layer (where a layer represents taking one additional bus), the first time the source frontier intersects with the target frontier, the combined path length is guaranteed to be minimal. The invariant maintained is that visMap[stop] always holds the minimum buses needed to reach that stop from the respective origin.
Pattern Reuse Notes
The Graph - Bidirectional BFS pattern used in this LeetCode 815 Solution is applicable to other hard pathfinding problems:
- LeetCode 126: Word Ladder II - Both problems involve finding the shortest transformation sequence. Bidirectional BFS significantly reduces the search space when the graph is dense or the branching factor is high.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 815
1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4#include <queue>
5
6using namespace std;
7
8class Solution {
9public:
10 int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
11 if (source == target) return 0;
12
13 // Map: Stop ID -> List of Bus Indices
14 unordered_map<int, vector<int>> stopToBuses;
15 for (int i = 0; i < routes.size(); ++i) {
16 for (int stop : routes[i]) {
17 stopToBuses[stop].push_back(i);
18 }
19 }
20
21 // Bidirectional BFS State
22 queue<int> qSource, qTarget;
23 unordered_map<int, int> distSource, distTarget;
24
25 qSource.push(source);
26 distSource[source] = 0;
27
28 qTarget.push(target);
29 distTarget[target] = 0;
30
31 // To avoid processing the same bus repeatedly in each direction
32 vector<bool> visitedBusSource(routes.size(), false);
33 vector<bool> visitedBusTarget(routes.size(), false);
34
35 while (!qSource.empty() && !qTarget.empty()) {
36 // Always expand the smaller queue
37 if (qSource.size() > qTarget.size()) {
38 if (expand(qTarget, distTarget, distSource, stopToBuses, routes, visitedBusTarget)) {
39 return distSource[lastIntersection] + distTarget[lastIntersection] + 1;
40 }
41 } else {
42 if (expand(qSource, distSource, distTarget, stopToBuses, routes, visitedBusSource)) {
43 return distSource[lastIntersection] + distTarget[lastIntersection] + 1;
44 }
45 }
46 }
47
48 return -1;
49 }
50
51private:
52 int lastIntersection = -1;
53
54 // Helper to expand one level of BFS
55 bool expand(queue<int>& q, unordered_map<int, int>& currentDist,
56 unordered_map<int, int>& otherDist,
57 unordered_map<int, vector<int>>& stopToBuses,
58 vector<vector<int>>& routes, vector<bool>& visitedBuses) {
59
60 int size = q.size();
61 while (size--) {
62 int currStop = q.front();
63 q.pop();
64
65 int depth = currentDist[currStop];
66
67 for (int busID : stopToBuses[currStop]) {
68 if (visitedBuses[busID]) continue;
69 visitedBuses[busID] = true;
70
71 for (int nextStop : routes[busID]) {
72 // Check intersection
73 if (otherDist.count(nextStop)) {
74 lastIntersection = nextStop;
75 return true;
76 }
77
78 if (currentDist.find(nextStop) == currentDist.end()) {
79 currentDist[nextStop] = depth + 1;
80 q.push(nextStop);
81 }
82 }
83 }
84 }
85 return false;
86 }
87};Java Solution for LeetCode 815
1import java.util.*;
2
3class Solution {
4 public int numBusesToDestination(int[][] routes, int source, int target) {
5 if (source == target) return 0;
6
7 // Map: Stop ID -> List of Bus Indices
8 Map<Integer, List<Integer>> stopToBuses = new HashMap<>();
9 for (int i = 0; i < routes.length; i++) {
10 for (int stop : routes[i]) {
11 stopToBuses.computeIfAbsent(stop, k -> new ArrayList<>()).add(i);
12 }
13 }
14
15 // Queues for BFS
16 Queue<Integer> qSource = new LinkedList<>();
17 Queue<Integer> qTarget = new LinkedList<>();
18 qSource.offer(source);
19 qTarget.offer(target);
20
21 // Maps to track depth: Stop ID -> Depth
22 Map<Integer, Integer> distSource = new HashMap<>();
23 Map<Integer, Integer> distTarget = new HashMap<>();
24 distSource.put(source, 0);
25 distTarget.put(target, 0);
26
27 // Visited arrays for buses to prevent cycles/redundancy
28 boolean[] visitedBusSource = new boolean[routes.length];
29 boolean[] visitedBusTarget = new boolean[routes.length];
30
31 while (!qSource.isEmpty() && !qTarget.isEmpty()) {
32 // Expand smaller queue
33 if (qSource.size() > qTarget.size()) {
34 int res = expand(qTarget, distTarget, distSource, stopToBuses, routes, visitedBusTarget);
35 if (res != -1) return res;
36 } else {
37 int res = expand(qSource, distSource, distTarget, stopToBuses, routes, visitedBusSource);
38 if (res != -1) return res;
39 }
40 }
41
42 return -1;
43 }
44
45 private int expand(Queue<Integer> q, Map<Integer, Integer> currentDist,
46 Map<Integer, Integer> otherDist,
47 Map<Integer, List<Integer>> stopToBuses,
48 int[][] routes, boolean[] visitedBuses) {
49
50 int size = q.size();
51 for (int i = 0; i < size; i++) {
52 int currStop = q.poll();
53 int depth = currentDist.get(currStop);
54
55 if (!stopToBuses.containsKey(currStop)) continue;
56
57 for (int busID : stopToBuses.get(currStop)) {
58 if (visitedBuses[busID]) continue;
59 visitedBuses[busID] = true;
60
61 for (int nextStop : routes[busID]) {
62 // Check intersection
63 if (otherDist.containsKey(nextStop)) {
64 return depth + 1 + otherDist.get(nextStop);
65 }
66
67 if (!currentDist.containsKey(nextStop)) {
68 currentDist.put(nextStop, depth + 1);
69 q.offer(nextStop);
70 }
71 }
72 }
73 }
74 return -1;
75 }
76}Python Solution for LeetCode 815
1from collections import defaultdict, deque
2
3class Solution:
4 def numBusesToDestination(self, routes: list[list[int]], source: int, target: int) -> int:
5 if source == target:
6 return 0
7
8 # Map: Stop ID -> List of Bus Indices
9 stop_to_buses = defaultdict(list)
10 for i, route in enumerate(routes):
11 for stop in route:
12 stop_to_buses[stop].append(i)
13
14 # Bidirectional BFS State
15 # Queues store stops
16 q_source = deque([source])
17 q_target = deque([target])
18
19 # Maps store stop -> buses taken
20 dist_source = {source: 0}
21 dist_target = {target: 0}
22
23 # Visited sets for buses to avoid reprocessing routes
24 vis_bus_source = set()
25 vis_bus_target = set()
26
27 def expand(q, current_dist, other_dist, visited_buses):
28 # Process one level
29 for _ in range(len(q)):
30 curr_stop = q.popleft()
31 depth = current_dist[curr_stop]
32
33 for bus_id in stop_to_buses[curr_stop]:
34 if bus_id in visited_buses:
35 continue
36 visited_buses.add(bus_id)
37
38 for next_stop in routes[bus_id]:
39 # Intersection found
40 if next_stop in other_dist:
41 return depth + 1 + other_dist[next_stop]
42
43 if next_stop not in current_dist:
44 current_dist[next_stop] = depth + 1
45 q.append(next_stop)
46 return -1
47
48 while q_source and q_target:
49 # Expand the smaller queue
50 if len(q_source) > len(q_target):
51 res = expand(q_target, dist_target, dist_source, vis_bus_target)
52 else:
53 res = expand(q_source, dist_source, dist_target, vis_bus_source)
54
55 if res != -1:
56 return res
57
58 return -1