833. Bus Routes¶

Difficulty: Hard

833. Bus Routes

Hard

You are given an array routes representing bus routes where routes[i] is a bus route that the i^th bus repeats forever.

For example, if routes[0] = [1, 5, 7], this means that the 0^th 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 <= 10⁵
All the values of routes[i] are unique.
sum(routes[i].length) <= 10⁵
0 <= routes[i][j] < 10⁶
0 <= source, target < 10⁶

Solution¶

class Solution {
    static class Pair {
        int node, cost;
        public Pair(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }
        @Override
        public String toString() {
            return "(" + node + " " + cost + ")";
        }
    }

    static class customSort implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            int op1 = Integer.compare(first.cost, second.cost);
            return op1;
        }
    }

    private ArrayList<ArrayList<Pair>> adj;

    public int numBusesToDestination(int[][] routes, int source, int target) {
        int n = routes.length;
        if (source == target)
            return 0;

        adj = new ArrayList<>();
        for (int i = 0; i <= routes.length; i++)
            adj.add(new ArrayList<>());

        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            for (int ele : routes[i - 1]) {
                if (!map.containsKey(ele)) 
                    map.put(ele, new ArrayList<>());
                map.get(ele).add(i);
            }
        }

        int dist[] = new int[(int)(n + 1)];
        Arrays.fill(dist, (int)(1e9));

        PriorityQueue<Pair> pq = new PriorityQueue<>(new customSort());
        for (Map.Entry<Integer, ArrayList<Integer>> curr : map.entrySet()) {
            ArrayList<Integer> val = new ArrayList<>();
            val = curr.getValue();
            for (int i = 0; i < val.size() - 1; i++) {
                int u = val.get(i), v = val.get(i + 1);
                if (u == v) continue;
                adj.get(u).add(new Pair(v, 1));
                adj.get(v).add(new Pair(u, 1));
            }
            if (val.size() > 1) {
                int u = val.get(0), v = val.get(val.size() - 1);
                if (u == v) continue;
                adj.get(u).add(new Pair(v, 1));
                adj.get(v).add(new Pair(u, 1));
            }

            if (curr.getKey() == source) {
                for (int ele : val) {
                    dist[ele] = 0;
                    pq.offer(new Pair(ele, 0));
                }
            }
        }

        while (pq.size() > 0){
            int currNode = pq.peek().node, currCost = pq.peek().cost;
            pq.poll();
            for (int i = 0; i < adj.get(currNode).size(); i++) {
                int childNode = adj.get(currNode).get(i).node;
                int childDist = adj.get(currNode).get(i).cost;
                if (dist[childNode] > childDist + currCost) {
                    dist[childNode] = childDist + currCost;
                    pq.offer(new Pair(childNode, dist[childNode]));
                } 
            }
        }

        int mini = Integer.MAX_VALUE;
        boolean flag = false;
        for (Map.Entry<Integer, ArrayList<Integer>> curr : map.entrySet()) {
            ArrayList<Integer> val = new ArrayList<>();
            val = curr.getValue();
            if (curr.getKey() == target) {
                for (int ele : val) {
                    if (dist[ele] != (int)(1e9)) flag = true;
                    mini = Math.min(mini, dist[ele]);
                }
            }
        }
        if (flag == false) return -1;
        return mini + 1;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here