12.11.2023
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/401
Problem TLDR
Minimum buses to travel by given routes
Intuition
The Breadth-First Search in a routes graph would work.
Build stop to route
association to know which of the routes are next.
Approach
Some optimizations:
eliminate the trivial case
source == target
remove a visited stop from
stopToRoute
graphthere is at most
routes.size
buses neededremember the visited stop
Complexity
Time complexity:
O(RS)Space complexity:
O(RS)
Code
fun numBusesToDestination(routes: Array<IntArray>, source: Int, target: Int): Int {
if (source == target) return 0
val stopToRoute = mutableMapOf<Int, MutableList<Int>>()
for (i in routes.indices)
for (stop in routes[i])
stopToRoute.getOrPut(stop) { mutableListOf() } += i
return with(ArrayDeque<Int>()) {
add(source)
val visited = mutableSetOf<Int>()
for (bus in 1..routes.size)
repeat(size) {
for (route in stopToRoute.remove(removeFirst()) ?: emptyList())
if (visited.add(route)) for (s in routes[route])
if (s == target) return@with bus else add(s)
}
-1
}
}