Bus Routes

Hard · Graphs · Explanation and code example

Breadth First Search (Routes as Nodes)

How it works

Instead of treating stops as nodes, we can treat bus routes as nodes. Two routes are connected if they share at least one common stop (you can transfer between them). This transforms the problem into finding the shortest path between any route containing the source stop and any route containing the target stop.

This approach can be more efficient when there are many stops but fewer routes, as we traverse through routes rather than individual stops.

Steps

  1. If source equals target, return 0.
  2. Build a mapping from each stop to the list of routes serving it.
  3. Build an adjacency list between routes: two routes are neighbors if they share a stop.
  4. Start BFS from all routes that contain the source stop.
  5. For each level of BFS:
    • Check if the current route contains the target stop; if so, return the current distance.
    • Add all neighboring routes (connected via shared stops) to the queue.
  6. If BFS completes without finding a route containing the target, return -1.

Complexity

  • Time complexity: O(n ^ 2 + n * m)
  • Space complexity: O(n ^ 2 + n * m)

Where n is the number of routes and m is the maximum number of stops per bus route.

Things to watch for

Forgetting the Source Equals Target Edge Case

If the source and target are the same stop, no bus is needed. Forgetting this check causes unnecessary computation or incorrect results when the BFS never finds the target in its traversal.

Counting Stops Instead of Bus Transfers

The problem asks for minimum number of buses, not minimum stops visited. A common mistake is incrementing the counter for each stop rather than each bus transfer.

Not Tracking Both Visited Buses and Visited Stops

Only tracking visited stops leads to revisiting the same bus multiple times, causing TLE. Only tracking visited buses may revisit stops unnecessarily. Both sets are needed for efficiency.

Incorrect BFS Level Counting

Incrementing the bus count at the wrong position (before checking if target is reached, or inside the wrong loop) leads to off-by-one errors in the result.

Building Inefficient Route Adjacency Graph

When using routes as nodes, failing to deduplicate edges between routes that share multiple stops creates redundant work and can cause memory issues with large inputs.

Python code example

from typing import List
from collections import defaultdict, deque

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0

        n = len(routes)
        adjList = [[] for _ in range(n)]
        stopToRoutes = defaultdict(list)
        for bus, route in enumerate(routes):
            for stop in route:
                stopToRoutes[stop].append(bus)

        if target not in stopToRoutes or source not in stopToRoutes:
            return -1

        hasEdge = [[False] * n for _ in range(n)]
        for buses in stopToRoutes.values():
            for i in range(len(buses)):
                for j in range(i + 1, len(buses)):
                    if hasEdge[buses[i]][buses[j]]:
                        continue
                    hasEdge[buses[i]][buses[j]] = True
                    hasEdge[buses[j]][buses[i]] = True
                    adjList[buses[i]].append(buses[j])
                    adjList[buses[j]].append(buses[i])

        q = deque([node for node in stopToRoutes[source]])
        res = 1
        while q:
            for _ in range(len(q)):
                node = q.popleft()
                if node in stopToRoutes[target]:
                    return res
                while adjList[node]:
                    nxtBus = adjList[node].pop()
                    if adjList[nxtBus]:
                        q.append(nxtBus)
            res += 1

        return -1

C++ code example

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) return 0;

        int n = routes.size();
        vector<vector<int>> adjList(n);
        unordered_map<int, vector<int>> stopToRoutes;
        for (int bus = 0; bus < n; bus++) {
            for (int stop : routes[bus]) {
                stopToRoutes[stop].push_back(bus);
            }
        }

        if (!stopToRoutes.count(source) || !stopToRoutes.count(target)) return -1;

        vector<vector<bool>> hasEdge(n, vector<bool>(n, false));
        for (auto& [stop, buses] : stopToRoutes) {
            for (int i = 0; i < (int)buses.size(); i++) {
                for (int j = i + 1; j < (int)buses.size(); j++) {
                    int b1 = buses[i], b2 = buses[j];
                    if (!hasEdge[b1][b2]) {
                        hasEdge[b1][b2] = hasEdge[b2][b1] = true;
                        adjList[b1].push_back(b2);
                        adjList[b2].push_back(b1);
                    }
                }
            }
        }

        queue<int> q;
        for (int bus : stopToRoutes[source]) q.push(bus);

        int res = 1;
        while (!q.empty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                int node = q.front(); q.pop();
                if (find(stopToRoutes[target].begin(), stopToRoutes[target].end(), node) != stopToRoutes[target].end()) {
                    return res;
                }
                while (!adjList[node].empty()) {
                    int nxtBus = adjList[node].back();
                    adjList[node].pop_back();
                    if (!adjList[nxtBus].empty()) {
                        q.push(nxtBus);
                    }
                }
            }
            res++;
        }
        return -1;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations