Bus Routes

Problem Statement

In this task, you are working with a set of bus routes where each bus embarks on a specified sequence of bus stops continuously and indefinitely. Every route in the array routes signifies a unique bus route where each bus circles through its stops over and over. Each route is represented by a list of bus stops. For instance, routes[0] = [1, 5, 7] indicates that bus number 0 continuously travels through stops 1, 5, and 7 in that sequence.

Starting from a bus stop named source, where no immediate bus is available (i.e., you're not aboard any bus from the start), your objective is to travel to a bus stop named target using as few bus transfers as possible. The function should return the minimum number of bus rides required to reach the target. If it's impossible to reach the target from the source using the available routes, the function should return -1.

Examples

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

Approach and Intuition

To solve this problem, a graph traversal algorithm is generally an efficient method, possibly a breadth-first search (BFS) that explores the shortest path first:

1. Understanding the problem with the graph perspective: Consider each bus stop as a node and each bus route as an edge connecting the stops it services. Your task is to find the shortest path (minimum edges traversed) from the source node to the target node.

2. Building the graph: Map each bus stop to the list of buses that pass through it. This way, you can navigate from one stop to other stops on the same route efficiently and determine possible transfers.

3. Generating the BFS algorithm:

   • Utilize a queue to explore each stop, starting from the source.
   • Track visited stops to prevent processing the same stop multiple times.
   • For each stop, examine the bus routes that service it, and then explore all other stops serviced by those buses, marking them as visited and adding them to the queue.
   • If you reach the target stop, return the number of buses (or edges) taken to get there.

4. Optimization considerations:

   • As the number of bus stops and routes can be quite large, aim to keep the space and time complexity manageable by only storing necessary information like visited stops and bus-route connectivity.

5. Early termination: If the source is the same as target, the result is immediately 0 as no travel is needed.

this approach ensures that we utilize each bus route effectively and navigate through the least number of bus changes, leveraging the unique routes provided and large possible values within the constraints. It handles non-direct routes and cases where some stops might be isolated or far away in terms of bus transfers from the target.

Solutions

class Solution {
public:
    vector<int> adjacencyList[501];
    
    void buildGraph(vector<vector<int>>& routes) {
        for (int i = 0; i < routes.size(); i++) {
            for (int j = i + 1; j < routes.size(); j++) {
                if (shareCommonStop(routes[i], routes[j])) {
                    adjacencyList[i].push_back(j);
                    adjacencyList[j].push_back(i);
                }
            }
        }
    }
    
    bool shareCommonStop(vector<int>& route1, vector<int>& route2) {
        int i = 0, j = 0;
        while (i < route1.size() && j < route2.size()) {
            if (route1[i] == route2[j]) {
                return true;
            }
    
            route1[i] < route2[j] ? i++ : j++;
        }
        return false;
    }
    
    void enqueueRoutes(queue<int>& q, vector<vector<int>>& routes, int source) {
        for (int i = 0; i < routes.size(); i++) {
            if (containsStop(routes[i], source)) {
                q.push(i);
            }
        }
    }
    
    bool containsStop(vector<int>& route, int stop) {
        for (int j = 0; j < route.size(); j++) {
            if (route[j] == stop) {
                return true;
            }
        }
        return false;
    }
    
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) {
            return 0;
        }
    
        for (int i = 0; i < routes.size(); ++i) {
            sort(routes[i].begin(), routes[i].end());
        }
    
        buildGraph(routes);
    
        queue<int> q;
        enqueueRoutes(q, routes, source);
    
        vector<int> visited(routes.size(), 0);
        int buses = 1;
        while (!q.empty()) {
            int sz = q.size();
    
            while (sz--) {
                int node = q.front();
                q.pop();
    
                if (containsStop(routes[node], target)) {
                    return buses;
                }
    
                for (int adj : adjacencyList[node]) {
                    if (!visited[adj]) {
                        visited[adj] = 1;
                        q.push(adj);
                    }
                }
            }
    
            buses++;
        }
    
        return -1;
    }
};