Bus Routes Leetcode Solution

Difficulty Level Hard
Frequently asked in Amazon Google Square Uber
Array Breadth First Search HashingViews 6124

Problem Statement

The Bus Routes LeetCode Solution – “Bus Routes” states that you’re given an array of routes where routes[i] is a bus route such that ith bus repeats the route forever. We’ll be given a bus stop source and we want to reach the bus stop target. We can travel between bus stops using buses only.

We need to find the least number of buses that are needed to travel from source to target. Return -1 if this is not possible.

Example:

Input:  routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2

Explanation:

  • We can switch from the first bus to the second bus when we reach 7 with bus1, and then we will move to target = 6 from the second bus.
  • Hence, our answer is 2.
Input:  routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1

Explanation:

  • There are no bus routes that can travel from source = 15 to target = 12, hence we return -1.

Approach

Idea:

  1. The main idea to solve this problem is to use Breadth-First Search.
  2. Store the mapping of each route[i] to the bus number and perform the breadth-first search for the buses.
  3. We’ll start from the source route position and push all those routed that we can travel from this source into the queue. All such routes can be easily obtained with the help of adjacent lists.
  4. Each time, pop the front element of the queue and iterate in the adjacency lists to find all the next routes that we can go from the current state with the count of a number of buses as a current number of buses + 1.
  5. Finally, we’ll end up with the least number of buses required to reach the target route.

Code

Bus Routes Leetcode C++ Solution:

class Solution {
public:
    const int N = 1e6;
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if(source==target){
            return 0;
        }
        int n = routes.size();
        vector<int> buses(n),adj[N];
        for(int i=0;i<n;i++){
            for(int j=0;j<routes[i].size();j++){
                adj[routes[i][j]].push_back(i);
            }
        }
        queue<pair<int,int>> q;
        for(auto& bus:adj[source]){
            for(auto& route:routes[bus]){
                q.push({route,1});
            }
            buses[bus] = true;
        }
        while(!q.empty()){
            int route = q.front().first,amount = q.front().second;
            q.pop();   
            if(route==target){
                return amount;
            }
            for(auto& bus:adj[route]){
                if(!buses[bus]){
                    buses[bus] = true;
                    for(auto& x:routes[bus]){
                        q.push({x,amount+1});
                    }
                }
            }
        }
        return -1;
    }
};

Bus Routes Leetcode Java Solution:

class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
        int n = routes.length;
        HashMap<Integer, HashSet<Integer>> to_routes = new HashMap<>();
        for (int i = 0; i < routes.length; ++i) {
            for (int j : routes[i]) {
                if (!to_routes.containsKey(j))
                    to_routes.put(j, new HashSet<Integer>());
                to_routes.get(j).add(i);
            }
        }
        Queue<int[]> bfs = new ArrayDeque();
        bfs.offer(new int[] {S, 0});
        HashSet<Integer> seen = new HashSet<>();
        seen.add(S);
        boolean[] seen_routes = new boolean[n];
        while (!bfs.isEmpty()) {
            int stop = bfs.peek()[0], bus = bfs.peek()[1];
            bfs.poll();
            if (stop == T) return bus;
            for (int i : to_routes.get(stop)) {
                if (seen_routes[i]) continue;
                for (int j : routes[i]) {
                    if (!seen.contains(j)) {
                        seen.add(j);
                        bfs.offer(new int[] {j, bus + 1});
                    }
                }
                seen_routes[i] = true;
            }
        }
        return -1;
    }
}

Complexity Analysis for Bus Routes Leetcode Solution

Time Complexity

The time complexity of the above code is as the Breadth-first Search of the normal graph.

Space Complexity

The space complexity of the above code is O(N), for storing the adjacency lists, where N = max route seen.

Reference: https://en.wikipedia.org/wiki/Breadth-first_search

Translate »