# Bus Routes **Difficulty:** HARD [External](https://leetcode.com/problems/bus-routes) Canonical: https://scaleengineer.com/dsa/problems/bus-routes **Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search) **Data structures:** Array, Hash Table **Companies:** [Coupang](https://scaleengineer.com/companies/coupang), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Info Edge](https://scaleengineer.com/companies/info-edge), [PhonePe](https://scaleengineer.com/companies/phonepe), [BitGo](https://scaleengineer.com/companies/bitgo), [Pinterest](https://scaleengineer.com/companies/pinterest) --- ## Problem 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 the `0th` bus travels in the sequence `1 -> 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) <= 105` * `0 <= routes[i][j] < 106` * `0 <= source, target < 106` # Approaches ## Brute-Force Graph Construction and BFS 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. **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. **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). ### Explanation 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. ```java class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } int n = routes.length; java.util.List> 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 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 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; } } ``` ### Algorithm - If `source` is the same as `target`, 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 `HashSet` for O(1) average time lookups. - If a common stop is found, add an edge between route `i` and route `j` in 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 `source` stop. Use a `visited` array 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 `target` stop, 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. ## BFS on Routes with Stop-to-Route Map 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. **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. **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. ### Explanation 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. ```java class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } int n = routes.length; java.util.Map> 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 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; } } ``` ### Algorithm - If `source == target`, return 0. - Create a map `stopToRoutes` where 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 `visitedRoutes` array/set to track visited routes. - Find all routes that contain the `source` stop using the `stopToRoutes` map. 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 `currentRoute` dequeued from the queue: - First, check if this route contains the `target` stop. If yes, return the current `buses` count. - If not, find all transferable routes. Iterate through each `stop` in `currentRoute`. - For each `stop`, use `stopToRoutes` to get all `nextRoute`s that also pass through this stop. - If a `nextRoute` has not been visited, mark it as visited and add it to the queue. - After a full level is processed, increment `buses`. - If the queue becomes empty and the target was not found, return -1. ## Optimized BFS on Stops and 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. **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. **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. ### Explanation 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 `nextStop`s 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. ```java class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } java.util.Map> 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 q = new java.util.LinkedList<>(); q.offer(source); java.util.Set 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 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; } } ``` ### Algorithm - If `source == target`, return 0. - Create the `stopToRoutes` map as in the previous approach. - Initialize a BFS queue with the `source` stop itself. - Use two sets to keep track of visited states: `visitedStops` and `visitedRoutes`. - Initialize `visitedStops` with the `source` stop. - 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 `currentStop` dequeued: - Look up all routes that pass through it using `stopToRoutes`. - For each `route` found, if it's in `visitedRoutes`, skip it. - Otherwise, mark the `route` as visited. - Now, iterate through all `nextStop`s on this newly explored route. - If a `nextStop` is the `target`, we have found the solution. Return the current `buses` count. - If a `nextStop` is not in `visitedStops`, add it to the set and enqueue it for the next level of the BFS. - If the BFS completes, the target is unreachable. Return -1. # Solutions ### CSharp ```csharp 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; } } ``` ### Java ```java class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } int n = routes.length; Set[] s = new Set[n]; List[] g = new List[n]; Arrays.setAll(s, k->new HashSet<>()); Arrays.setAll(g, k->new ArrayList<>()); Map> 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 q = new ArrayDeque<>(); Set 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; } } ``` ### CPP ```cpp class Solution { public: int numBusesToDestination(vector> &routes, int source, int target) { if (source == target) { return 0; } int n = routes.size(); vector> s(n); vector> g(n); unordered_map> 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 q; unordered_set 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; } }; ``` ### Python ```python 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 - 1 ```