LeetCode Entry

815. Bus Routes

12.11.2023 hard 2023 kotlin

Minimum buses to travel by given routes

815. Bus Routes hard blog post substack image.png

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 graph
  • there is at most routes.size buses needed
  • remember 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
      }
    }