• Posts

Problem 815 Bus Routes

Problem Statement

Link - Problem 815

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

Solution

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

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

        queue<int> q;
        unordered_set<int> vis;
        for (auto route : adjList[source]) {
            q.push(route);
            vis.insert(route);
        }

        int busCount = 1;
        while (q.size()) {
            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 : adjList[stop]) {
                        if (!vis.count(nextRoute)) {
                            vis.insert(nextRoute);
                            q.push(nextRoute);
                        }
                    }
                }
            }
            busCount++;
        }
        return -1;
    }
};

Complexity Analysis

| Algorithm                  | Time Complexity | Space Complexity |
| -------------------------- | --------------- | ---------------- |
| Breadth-First Search (BFS) | O(n _ m _ k)    | O(n + m)         |

Explanation

Intial Thoughts

To solve this problem, think of it like navigating through a city with multiple bus routes. The goal is to find the shortest path from the source to the target. Consider that each bus stop can be a meeting point for multiple buses, and we need to find the least number of buses to take to reach the target. Think about creating a map or a network where bus stops are connected if they are on the same bus route.

Intuitive Analysis

Imagine you are actually traveling through the city. You start at the source and look for buses that stop there. Each bus represents a possible path, and you need to transfer between buses to reach the target. Think of each transfer as moving to a new bus route. The key is to find the sequence of buses that leads to the target with the fewest transfers. Consider using a strategy like breadth-first search to explore all possible paths level by level, starting from the source, to ensure we find the shortest path.

1. Intuition

• The problem can be approached by modeling the bus routes as a graph where each bus stop is a node and two nodes are connected if they are on the same bus route.
• We need to find the shortest path between the source and target nodes in this graph, where the weight of each edge is 1.
• Since we can only travel between bus stops by buses, we need to consider the bus routes as the edges in the graph.
• The key insight is to use a breadth-first search (BFS) algorithm to find the shortest path between the source and target nodes.
• We start by adding all the bus routes that pass through the source node to the queue, and then iteratively add the neighboring nodes to the queue.
• We keep track of the number of buses taken to reach each node, and return the minimum number of buses taken to reach the target node.
• If there is no path from the source to the target node, we return -1.

2. Implementation

• We use an unordered_map<int, vector<int>> adjList to store the adjacency list of the graph, where each key is a bus stop and the value is a list of bus routes that pass through it.
• We use a queue<int> to store the bus routes to be processed, and an unordered_set<int> to keep track of the visited bus routes.
• We start by adding all the bus routes that pass through the source node to the queue and vis set.
• We then enter a loop where we process each bus route in the queue, and add its neighboring nodes to the queue and vis set.
• We use a busCount variable to keep track of the number of buses taken to reach each node.
• We return the busCount when we reach the target node, or -1 if there is no path from the source to the target node.
• The time complexity of this solution is O(n * m), where n is the number of bus routes and m is the maximum number of bus stops in a route.

Complexity Analysis

Time Complexity:

• The algorithm iterates over each route in routes and for each route, it iterates over each stop. This results in a time complexity of O(n _ m), where n is the number of routes and m is the average number of stops per route. Additionally, for each stop, it iterates over each nextRoute in the adjacency list, leading to an additional factor of k, where k is the average number of routes per stop, resulting in an overall time complexity of O(n _ m * k).
• The dominant operations in the algorithm are the nested loops iterating over routes, stops, and nextRoutes, as well as the queue operations (q.push and q.pop) and set operations (vis.insert and vis.count), all of which are constant time or linear in the size of the input.
• The Big O classification of O(n _ m _ k) is justified because the algorithm’s running time grows linearly with the size of the input, where the input size is represented by the number of routes (n), the average number of stops per route (m), and the average number of routes per stop (k).

Space Complexity:

• The algorithm uses an adjList to store the adjacency list representation of the graph, an unordered_set to keep track of visited routes, and a queue to store the routes to be visited. The space complexity is dominated by the size of the adjList and the vis set, which store at most n routes and m stops.
• The impact of the data structures used in the algorithm is significant, as the adjList and vis set allow for efficient lookups and insertions. The use of an unordered_map for adjList and an unordered_set for vis results in an average time complexity of O(1) for these operations.
• The space complexity of O(n + m) is justified because the algorithm stores at most n routes and m stops in the adjList and vis set, resulting in a linear space complexity with respect to the size of the input.

Footnote

This question is rated as Hard difficulty.

Similar Questions: