815. Bus Routes

Version #1 BFS on buses

• 1 <= routes.length <= 500.
• 1 <= routes[i].length <= 500.
• 0 <= routes[i][j] < 10 ^ 6.

I choose to store buses instead of stops is because that number of stops worst case is 500*500 if they are all distinct
However the number is buses is only 500
So considering the Space complexity, I used bus number to represent the state

We visit all bus at most twice
Time O(#buses)

38.92 %
class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
        if (S == T) return 0;
        // if we are at bus j, then we can travel to any stop that can be reached by bus j
        // Which means we can trafer to any of the buses that stop by all those stops
        // routes[j] -> stop number that we can reach by taking bus[j]
        Map<Integer, Set<Integer>> stopToBus = new HashMap<>();
        for (int j = 0; j < routes.length; j++) { // bus[j]
            for (int i = 0; i < routes[j].length; i++) { // routes[j][i] -> stop number
                stopToBus.putIfAbsent(routes[j][i], new HashSet<>());
                stopToBus.get(routes[j][i]).add(j);
            }
        }
        // que of bus
        Set<Integer> taken = new HashSet<>();
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> que = new LinkedList<>();
        Set<Integer> buses = stopToBus.get(S);
        for (int bus : buses) {
            que.offer(bus);
        }
        int level = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            level++;
            while (size-- > 0) {
                int bus = que.poll();
                for (int i = 0; i < routes[bus].length; i++) { // stops that can be reached by current bus
                    if (routes[bus][i] == T) return level;
                    if (visited.add(routes[bus][i])) { // this stop is never reached before
                        buses = stopToBus.get(routes[bus][i]);
                        for (int nextBus : buses) {
                            if (taken.add(nextBus)) { // this bus is never taken before
                                que.offer(nextBus);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
}