Bus Routes

Leetcode Problem 815: Bus Routes

Problem Summary

You are given bus routes where routes[i] is the ordered list of stops the i-th bus visits in a repeating loop. Starting at bus stop source (not on any bus), find the minimum number of buses you must board to reach bus stop target. Return -1 if it is impossible.

Constraints:

• There are between 1 and 500 bus routes.
• Each route has between 1 and 100,000 stops; the total number of stops across all routes is at most 100,000.
• All stop IDs within a single route are unique and are non-negative integers less than 1,000,000.
• Both source and target are valid stop IDs.

Techniques

• Array
• Hash Table
• Breadth-First Search

Solution

function numBusesToDestination(routes: number[][], source: number, target: number): number {
    if (source === target) {
        return 0
    }

    let busesForEachStop = new Map<number, number[]>()

    for (let bus = 0; bus < routes.length; bus++) {
        let busRoute = routes[bus]

        for (let k = 0; k < busRoute.length; k++) {
            let stop = busRoute[k]

            if (busesForEachStop.has(stop)) {
               busesForEachStop.set(stop, [...busesForEachStop.get(stop)!, bus])     
            } else {
                busesForEachStop.set(stop, [bus])
            }
        }
    }

    let queue = busesForEachStop.get(source)
    let visitedStops = new Set<number>()
    let visitedBuses = new Set<number>(queue)
    let numberOfBusesNeeded = 1

    while (queue && queue.length > 0) {
        let currentNumberOfBuses = queue.length

        while (currentNumberOfBuses > 0) {
            let bus = queue.shift()!
            let busRoute = routes[bus]

            for (let stopPosition = 0; stopPosition < busRoute.length; stopPosition++) {
                let stop = busRoute[stopPosition]

                if (visitedStops.has(stop)) {
                    continue;
                }

                visitedStops.add(stop)

                if (stop === target) {
                    return numberOfBusesNeeded
                }

                const busesForStop = busesForEachStop.get(stop)!

                for (let busForStopPosition = 0; busForStopPosition < busesForStop.length; busForStopPosition++) {
                    let bus = busesForStop[busForStopPosition]
                    if (!visitedBuses.has(bus)) {
                        visitedBuses.add(bus)
                        queue.push(bus)
                    }
                }
            }

            currentNumberOfBuses--
        }

        numberOfBusesNeeded++
    }

    return -1
};

console.log(numBusesToDestination([[1,2,7],[3,6,7]], 1, 6)) // 2
console.log(numBusesToDestination([[7,12],[4,5,15],[6],[15,19],[9,12,13]], 15, 12)) // -1