bus_routes.ts

function numBusesToDestination(
    routes: number[][], 
    source: number, 
    target: number
): number {
    
    // 1 <= routes.length (n) <= 500.
    // 1 <= routes[i].length (m) <= 10^5

    // construct a hashmap for stops | O(m x n)
    // which grows to become a graph for transitions 
    let transitions = {
        // stop: [bus, bus, bus]
    } as Record<string, string[]>;

    // construct a hashmap for next stops of different buses
    let stops = [
        // { stop: next, stop: next, ... } <-- bus 0
        // { stop: next, stop: next, ... } <-- bus 1
    ] as Array<Record<string, number>>;

    for (let [bus, route] of Object.entries(routes)) {
        stops.push({});
        for (let i = 0, j = null; i < route.length; ++i) {
            const stop = route[i];
            const next = route[(i + 1) % route.length];
            if (!(stop in transitions))
                transitions[stop] = [];
            transitions[stop].push(bus);
            stops.at(-1)[stop] = next;
        }
    }
    
    // optimise the stops, instead of having to go through
    // intermediary stops in the dynamic part of the algorithm
    // it would save a lot of time if we can just jump directly
    // to the next stop at which there is a changeover, or,
    // jump directly to the target stop.
    const fast_stops = [
        // { stop: next (target or changeover stop), ... } <-- bus 0
        // { stop: next (target or changeover stop), ... } <-- bus 1
    ]

    // to support the creation of a fast next-stop object, we need
    // a set that contains the fast stops
    const fast = new Set(Object.entries(transitions)
        .filter(([_, t]) => t.length > 1).map(([s, _]) => parseInt(s)));
    fast.add(source);
    fast.add(target);

    // optimise routes to only include changeovers, start and end
    // (so called fast or optimised stops)
    routes = routes.map(route => route.filter(stop => fast.has(stop)))

    // generate the fast next-stop objects in the same manner we
    // did before, which will allow us to pass test case 41 onwards
    // in LeetCode
    for (let [bus, route] of Object.entries(routes)) {
        fast_stops.push({});
        for (let i = 0, j = null; i < route.length; ++i) {
            const stop = route[i];
            const next = route[(i + 1) % route.length];

            fast_stops.at(-1)[stop] = next;
        }
    }

    const fast_transitions = 
        Object.fromEntries(
            Object.entries(transitions)
                .filter(([stop, buses]) => fast.has(parseInt(stop))));

    // we choose breadth traversal of possibilities which correlates
    // better with the number of buses than depth search.
    const queue = [{
        stop: source,
        // no bus yet
        bus: null,
        // no bus changes yet
        changes: 0,
    }];

    // to avoid the exploration of paths from the same source twice
    // which can lead to exponential complexity.
    // this is the trickiest part of this problem, what to memoize
    // and why.
    // in this method we create a hash map with the key being a
    // combination of the bus we are on, the stop we are at, and
    // the total number of changes so far.
    const explored = new Map<string, number>();

    let bestAnswer = Infinity;

    while (queue.length > 0) {
        // operating this like a queue using shift()/push()
        const { stop, bus, changes } =  queue.shift();

        if (stop === target && changes < bestAnswer) {
            bestAnswer = changes;
            continue;
        }

        if (changes > bestAnswer)
            continue;

        if (explored.has(`${bus}-${stop}`) &&
            changes >= explored.get(`${bus}-${stop}`))
            continue;

        // OPTIMISATION: switched from transitions to fast_transitions
        for (let newBus of fast_transitions[stop]) {
            // OPTIMISATION: switched from stops to fast_stops
            const newStop = fast_stops[newBus][stop];
            let newChanges = changes;
            if (newBus !== bus)
                ++newChanges;

            queue.push({
                stop: newStop,
                changes: newChanges,
                bus: newBus,
            });
        }
        explored.set(`${bus}-${stop}`, changes);
    }

    return isFinite(bestAnswer) ? bestAnswer : -1;
};