Bus Routes
HardPrompt
You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.
- For example, if
routes[0] = [1, 5, 7], this means that the0thbus travels in the sequence1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...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.
Example 1:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.Example 2:
Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1
Constraints:
1 <= routes.length <= 500.1 <= routes[i].length <= 105- All the values of
routes[i]are unique. sum(routes[i].length) <= 1050 <= routes[i][j] < 1060 <= source, target < 106
Approaches
3 approaches with complexity analysis and trade-offs.
This approach models the problem as finding the shortest path in a graph where bus routes are nodes. An edge exists between two routes if they share a stop. First, we build this graph by checking every pair of routes for common stops. Then, we perform a Breadth-First Search (BFS) starting from all routes that contain the source stop to find the shortest path to any route containing the target stop.
Algorithm
- If
sourceis the same astarget, return 0 as no travel is needed. - Model the problem as a graph where each bus route is a node. An edge exists between two nodes if their corresponding routes share at least one common bus stop.
- Construct an adjacency list for this graph. Iterate through every pair of routes
(i, j). - For each pair, check for a common stop. To do this efficiently, convert the stops of one route into a
HashSetfor O(1) average time lookups. - If a common stop is found, add an edge between route
iand routejin the adjacency list. - Once the graph is built, perform a Breadth-First Search (BFS) to find the shortest path.
- Initialize a queue with all routes that pass through the
sourcestop. Use avisitedarray to keep track of routes that have been added to the queue. - The BFS proceeds in levels. The initial level is 1, representing taking the first bus.
- In each level, dequeue a route. If this route contains the
targetstop, the current level number is the minimum number of buses required. Return this number. - If the route does not contain the target, add all of its unvisited neighboring routes to the queue.
- If the queue becomes empty and the target has not been reached, it means the target is unreachable. Return -1.
Walkthrough
The problem can be rephrased as finding the shortest path in a graph. The nodes of this graph are the bus routes, and an edge connects two routes if they share at least one bus stop. The length of a path is the number of nodes (buses) in it.
The first step is to construct this graph. We can use an adjacency list where adj[i] stores all routes connected to route i. We iterate through every possible pair of routes (i, j). For each pair, we check if they have a common stop. A simple way to do this is to iterate through all stops of routes[i] and see if any of them exist in routes[j]. To make the lookup in routes[j] efficient, we can convert its stops into a HashSet.
Once the graph is built, we perform a Breadth-First Search (BFS) to find the shortest path. The BFS starts from all routes that include the source stop. We use a queue and a visited array to keep track of routes. The search proceeds in levels, where level k represents all routes reachable by taking k buses. If we dequeue a route that contains the target stop, we have found the shortest path, and the current level is our answer. If the source and target are the same, 0 buses are needed. If the BFS finishes without reaching the target, it's impossible.
class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } int n = routes.length; java.util.List<java.util.List<Integer>> adj = new java.util.ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new java.util.ArrayList<>()); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (haveCommonStop(routes[i], routes[j])) { adj.get(i).add(j); adj.get(j).add(i); } } } java.util.Queue<Integer> q = new java.util.LinkedList<>(); boolean[] visited = new boolean[n]; for (int i = 0; i < n; i++) { if (isStopOnRoute(routes[i], source)) { q.offer(i); visited[i] = true; } } int buses = 1; while (!q.isEmpty()) { int size = q.size(); for (int i = 0; i < size; i++) { int route = q.poll(); if (isStopOnRoute(routes[route], target)) { return buses; } for (int neighbor : adj.get(route)) { if (!visited[neighbor]) { visited[neighbor] = true; q.offer(neighbor); } } } buses++; } return -1; } private boolean haveCommonStop(int[] route1, int[] route2) { java.util.Set<Integer> stops1 = new java.util.HashSet<>(); for (int stop : route1) { stops1.add(stop); } for (int stop : route2) { if (stops1.contains(stop)) { return true; } } return false; } private boolean isStopOnRoute(int[] route, int stop) { for (int s : route) { if (s == stop) { return true; } } return false; }}Complexity
Time
O(N^2 * L), where N is the number of routes and L is the maximum length of a route. Building the graph by comparing all pairs of routes takes O(N^2 * L). The subsequent BFS on the route graph takes O(V+E) = O(N+N^2) = O(N^2). The graph construction time dominates.
Space
O(N^2), where N is the number of routes. This space is required to store the adjacency list for the route-to-route graph, which can have up to O(N^2) edges.
Trade-offs
Pros
Conceptually simple to understand as it directly translates the problem into a standard graph traversal.
Cons
High time complexity due to the O(N^2 * L) graph construction step, which may be too slow for large inputs.
High space complexity to store the route-to-route adjacency list, which can be up to O(N^2).
This approach improves upon the first one by building the graph representation more efficiently. Instead of pairwise route comparisons, we first create a map from each bus stop to all routes that service it. Then, we perform a BFS on the routes. To find adjacent routes for a given route, we iterate through its stops and use the map to find all other routes that share those stops.
Algorithm
- If
source == target, return 0. - Create a map
stopToRouteswhere the key is a bus stop and the value is a list of all routes that service that stop. Populate this map by iterating through all routes. - Initialize a queue for BFS and a
visitedRoutesarray/set to track visited routes. - Find all routes that contain the
sourcestop using thestopToRoutesmap. Add these initial routes to the queue and mark them as visited. - Start the BFS with
buses = 1. - While the queue is not empty, process one level at a time.
- For each
currentRoutedequeued from the queue:- First, check if this route contains the
targetstop. If yes, return the currentbusescount. - If not, find all transferable routes. Iterate through each
stopincurrentRoute. - For each
stop, usestopToRoutesto get allnextRoutes that also pass through this stop. - If a
nextRoutehas not been visited, mark it as visited and add it to the queue.
- First, check if this route contains the
- After a full level is processed, increment
buses. - If the queue becomes empty and the target was not found, return -1.
Walkthrough
This method still treats bus routes as nodes in a graph and seeks the shortest path using BFS. The key improvement is in how we find adjacent nodes (connected routes) during the BFS traversal, avoiding the expensive pre-computation of the entire graph.
We start by creating a hash map, stopToRoutes, which maps each stop number to a list of route indices that pass through that stop. This can be built in a single pass over all routes and stops.
The BFS starts with a queue containing all routes that serve the source stop. We also maintain a visited set to avoid processing the same route multiple times. The BFS proceeds in levels, with buses = 1 for the first level. In each iteration of the main BFS loop, we process all routes currently in the queue (one level). For each currentRoute dequeued, we check if it contains the target. If it does, we've found our answer. If not, we find all connected routes. We do this by iterating through each stop in the currentRoute. For each stop, we use our stopToRoutes map to get a list of all routes that also pass through this stop. These are the adjacent routes. Any adjacent route that has not been visited yet is added to the queue for the next level and marked as visited. After processing all routes at the current level, we increment the buses count and proceed to the next level.
class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } int n = routes.length; java.util.Map<Integer, java.util.List<Integer>> stopToRoutes = new java.util.HashMap<>(); for (int i = 0; i < n; i++) { for (int stop : routes[i]) { stopToRoutes.computeIfAbsent(stop, k -> new java.util.ArrayList<>()).add(i); } } if (!stopToRoutes.containsKey(source)) { return -1; } java.util.Queue<Integer> q = new java.util.LinkedList<>(); boolean[] visitedRoutes = new boolean[n]; for (int route : stopToRoutes.get(source)) { q.offer(route); visitedRoutes[route] = true; } int buses = 1; while (!q.isEmpty()) { int size = q.size(); for (int i = 0; i < size; i++) { int currentRoute = q.poll(); // Check for target in all stops of the current route for (int stop : routes[currentRoute]) { if (stop == target) { return buses; } } // Add next unvisited routes for (int stop : routes[currentRoute]) { for (int nextRoute : stopToRoutes.get(stop)) { if (!visitedRoutes[nextRoute]) { visitedRoutes[nextRoute] = true; q.offer(nextRoute); } } } } buses++; } return -1; }}Complexity
Time
O(S + sum(C_s^2)), where S is the total number of stops and C_s is the count of routes for a stop `s`. Building the map is O(S). The BFS complexity is dominated by iterating through all neighbors for each stop on each visited route. In the worst case, this can be O(S + N^2).
Space
O(S + N), where S is the total number of stops across all routes and N is the number of routes. This space is for the `stopToRoutes` map, the queue, and the visited set.
Trade-offs
Pros
More efficient than brute-force graph construction, especially for sparse graphs.
Avoids storing the full O(N^2) route graph, saving space.
Cons
The time complexity can still be high if many routes share common stops, as this leads to re-evaluating the same connections multiple times.
The performance degrades in dense transportation networks where a single stop is a hub for many routes.
This is the most efficient approach. It performs a BFS where the states being explored are the bus stops themselves, but it intelligently avoids re-exploring entire bus routes. The levels of the BFS directly correspond to the number of buses taken.
Algorithm
- If
source == target, return 0. - Create the
stopToRoutesmap as in the previous approach. - Initialize a BFS queue with the
sourcestop itself. - Use two sets to keep track of visited states:
visitedStopsandvisitedRoutes. - Initialize
visitedStopswith thesourcestop. - The BFS proceeds in levels, where each level corresponds to taking one more bus. Initialize
buses = 0. - While the queue is not empty:
- Increment
buses. - Process all stops at the current level. For each
currentStopdequeued:- Look up all routes that pass through it using
stopToRoutes. - For each
routefound, if it's invisitedRoutes, skip it. - Otherwise, mark the
routeas visited. - Now, iterate through all
nextStops on this newly explored route. - If a
nextStopis thetarget, we have found the solution. Return the currentbusescount. - If a
nextStopis not invisitedStops, add it to the set and enqueue it for the next level of the BFS.
- Look up all routes that pass through it using
- Increment
- If the BFS completes, the target is unreachable. Return -1.
Walkthrough
This approach refines the BFS by changing the items in the queue from routes to stops. This allows for a more direct search from the source stop to the target stop. We use two sets to keep track of visited stops and visited routes to avoid redundant work.
First, we build the same stopToRoutes map as in the previous approach. The BFS queue is initialized with the source stop. We also have a visitedStops set, initialized with source. The search proceeds in levels, where level 0 has just the source stop. We maintain a buses counter, starting at 0.
In each step of the BFS, we increment buses and process all stops added in the previous level. For each currentStop dequeued, we look up all routes that pass through it using stopToRoutes. For each route found, if we haven't explored this route before (checked using a visitedRoutes set), we mark it as explored. Then, we iterate through all nextStops on this route. If a nextStop is the target, we have found the solution and return the current buses count. If nextStop has not been visited before (checked using visitedStops), we mark it as visited and add it to the queue for the next level. This ensures that each route is fully explored only once, and each stop is added to the queue only once, leading to an optimal time complexity.
class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } java.util.Map<Integer, java.util.List<Integer>> stopToRoutes = new java.util.HashMap<>(); for (int i = 0; i < routes.length; i++) { for (int stop : routes[i]) { stopToRoutes.computeIfAbsent(stop, k -> new java.util.ArrayList<>()).add(i); } } java.util.Queue<Integer> q = new java.util.LinkedList<>(); q.offer(source); java.util.Set<Integer> visitedStops = new java.util.HashSet<>(); visitedStops.add(source); boolean[] visitedRoutes = new boolean[routes.length]; int buses = 0; while (!q.isEmpty()) { buses++; int levelSize = q.size(); for (int i = 0; i < levelSize; i++) { int currentStop = q.poll(); java.util.List<Integer> availableRoutes = stopToRoutes.get(currentStop); if (availableRoutes == null) continue; for (int routeIndex : availableRoutes) { if (visitedRoutes[routeIndex]) { continue; } visitedRoutes[routeIndex] = true; for (int nextStop : routes[routeIndex]) { if (nextStop == target) { return buses; } if (!visitedStops.contains(nextStop)) { visitedStops.add(nextStop); q.offer(nextStop); } } } } } return -1; }}Complexity
Time
O(S + N), where S is the total number of stops across all routes and N is the number of routes. Building the map is O(S). The BFS processes each stop and each route at most once. The total work is the sum of iterating through all stop-to-route mappings and all route-to-stop mappings, which is bounded by O(S).
Space
O(S + N), where S is the total number of stops and N is the number of routes. Space is used for the `stopToRoutes` map, the queue, and the visited sets for both stops and routes.
Trade-offs
Pros
Most efficient time complexity among the presented approaches.
Traverses each part of the route network (each stop and each route) at most once, avoiding redundant computations.
Cons
The logic is slightly more complex as it requires managing visited states for both stops and routes.
Solutions
Solution
public class Solution { public int NumBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } Dictionary < int, HashSet < int >> stopToRoutes = new Dictionary < int, HashSet < int >> (); List < HashSet < int >> routeToStops = new List < HashSet < int >> (); for (int i = 0; i < routes.Length; i++) { routeToStops.Add(new HashSet < int > ()); foreach(int stop in routes[i]) { routeToStops[i].Add(stop); if (!stopToRoutes.ContainsKey(stop)) { stopToRoutes[stop] = new HashSet < int > (); } stopToRoutes[stop].Add(i); } } Queue < int > queue = new Queue < int > (); HashSet < int > visited = new HashSet < int > (); int ans = 0; foreach(int routeId in stopToRoutes[source]) { queue.Enqueue(routeId); visited.Add(routeId); } while (queue.Count > 0) { int count = queue.Count; ans++; for (int i = 0; i < count; i++) { int routeId = queue.Dequeue(); foreach(int stop in routeToStops[routeId]) { if (stop == target) { return ans; } foreach(int nextRoute in stopToRoutes[stop]) { if (!visited.Contains(nextRoute)) { visited.Add(nextRoute); queue.Enqueue(nextRoute); } } } } } return -1; }}class Solution {public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } int n = routes.length; Set<Integer>[] s = new Set[n]; List<Integer>[] g = new List[n]; Arrays.setAll(s, k->new HashSet<>()); Arrays.setAll(g, k->new ArrayList<>()); Map<Integer, List<Integer>> d = new HashMap<>(); for (int i = 0; i < n; ++i) { for (int v : routes[i]) { s[i].add(v); d.computeIfAbsent(v, k->new ArrayList<>()).add(i); } } for (var ids : d.values()) { int m = ids.size(); for (int i = 0; i < m; ++i) { for (int j = i + 1; j < m; ++j) { int a = ids.get(i), b = ids.get(j); g[a].add(b); g[b].add(a); } } } Deque<Integer> q = new ArrayDeque<>(); Set<Integer> vis = new HashSet<>(); int ans = 1; for (int v : d.get(source)) { q.offer(v); vis.add(v); } while (!q.isEmpty()) { for (int k = q.size(); k > 0; --k) { int i = q.pollFirst(); if (s[i].contains(target)) { return ans; } for (int j : g[i]) { if (!vis.contains(j)) { vis.add(j); q.offer(j); } } } ++ans; } return -1; }}class Solution {public: int numBusesToDestination(vector<vector<int>> &routes, int source, int target) { if (source == target) { return 0; } int n = routes.size(); vector<unordered_set<int>> s(n); vector<vector<int>> g(n); unordered_map<int, vector<int>> d; for (int i = 0; i < n; ++i) { for (int v : routes[i]) { s[i].insert(v); d[v].push_back(i); } } for (auto &[_, ids] : d) { int m = ids.size(); for (int i = 0; i < m; ++i) { for (int j = i + 1; j < m; ++j) { int a = ids[i], b = ids[j]; g[a].push_back(b); g[b].push_back(a); } } } queue<int> q; unordered_set<int> vis; int ans = 1; for (int v : d[source]) { q.push(v); vis.insert(v); } while (!q.empty()) { for (int k = q.size(); k; --k) { int i = q.front(); q.pop(); if (s[i].count(target)) { return ans; } for (int j : g[i]) { if (!vis.count(j)) { vis.insert(j); q.push(j); } } } ++ans; } return -1; }};class Solution : def numBusesToDestination ( self , routes : List [ List [ int ]], source : int , target : int ) -> int : if source == target : return 0 s = [ set ( r ) for r in routes ] d = defaultdict ( list ) for i , r in enumerate ( routes ): for v in r : d [ v ]. append ( i ) g = defaultdict ( list ) for ids in d . values (): m = len ( ids ) for i in range ( m ): for j in range ( i + 1 , m ): a , b = ids [ i ], ids [ j ] g [ a ]. append ( b ) g [ b ]. append ( a ) q = deque ( d [ source ]) ans = 1 vis = set ( d [ source ]) while q : for _ in range ( len ( q )): i = q . popleft () if target in s [ i ]: return ans for j in g [ i ]: if j not in vis : vis . add ( j ) q . append ( j ) ans += 1 return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.