• Link: https://leetcode.com/problems/bus-routes

Question

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|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|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

Approach 1: BFS with bus stops as nodes

Intuition

• Treat each bus route as a node in a graph.
• You can move from one route to another if they share a common stop.
• Use BFS starting from all routes containing the source stop.
• Each BFS level = taking one more bus.
• As soon as any visited route contains the target stop → return the number of buses used.

Algorithm

1. Build adj: stop → list of route indices that pass through that stop.
2. Initialize a queue with all routes that include source. Mark them visited.
3. BFS:
   • For each route in the current level:
     • If this route contains the target, return the current bus count.
     • For each stop in the route:
       • For each nextRoute passing through that stop:
         • If unvisited, push it into the queue.
   • Increase bus count after finishing the level.
4. If BFS finishes with no match, return -1.

Code

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

        unordered_map<int, vector<int>> adj;

        // i is route
        for (int i = 0 ; i < routes.size() ; i++) {
            for (auto stop: routes[i]) {
                adj[stop].push_back(i);
            }
        }

        unordered_set<int> visited;
        queue<int> q;

        for (auto route: adj[source]) {
            q.push(route);
            visited.insert(route);
        }

        int busCount = 1;

        while (!q.empty()) {
            int size = q.size();

            for (int i = 0 ; i < size ; i++) {
                int route = q.front();
                q.pop();

                for (auto stop: routes[route]) {
                    if (stop == target) {
                        return busCount;
                    }

                    for (auto nextRoute: adj[stop]) {
                        if (!visited.count(nextRoute)) {
                            visited.insert(nextRoute);
                            q.push(nextRoute);
                        }
                    }
                }
            }
            busCount++;
        }

        return -1;

    }
};

Complexity Analysis

Here, M is the size of routes, and K is the maximum size of routes[i].

• Time complexity: O(M2∗K)

  To store the routes for each stop we iterate over each route and for each route, we iterate over each stop, hence this step will take O(M∗K) time. In the BFS, we iterate over each route in the queue. For each route we popped, we will iterate over its stop, and for each stop, we will iterate over the connected routes in the map adjList, hence the time required will be O(M∗K∗M) or O(M2∗K).

• Space complexity: O(M⋅K)

  The map adjList will store the routes for each stop. There can be M⋅K number of stops in routes in the worst case (each of the M routes can have K stops), possibly with duplicates. When represented using adjList, each of the mentioned stops appears exactly once. Therefore, adjList contains an equal number of stop-route element pairs.

Reference

• Editorial for 815. Bus Routes