LeetCode Entry

1870. Minimum Speed to Arrive on Time

26.07.2023 medium 2023 kotlin

Max speed for all dist departing at round hours, be fit in hour

1870. Minimum Speed to Arrive on Time medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/287

Problem TLDR

Max speed for all dist departing at round hours, be fit in hour

Intuition

Given the speed, we can calculate the travel time in O(n). With decreasing speed the time grows, so we can do the Binary Search

Approach

For more robust Binary Search code:

  • use inclusive lo and hi
  • check the last condition lo == hi
  • always move the borders lo = mid + 1, hi = mid - 1
  • always save the result res = mid

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\)

Code


    fun minSpeedOnTime(dist: IntArray, hour: Double): Int {
        var lo = 1
        var hi = 1_000_000_000
        var res = -1
        while (lo <= hi) {
          val mid = lo + (hi - lo) / 2
          var dt = 0.0
          val time = dist.fold(0.0) { r, t ->
            r + Math.ceil(dt).also { dt = t / mid.toDouble() }
          } + dt
          if (hour >= time) {
            res = mid
            hi = mid - 1
          } else lo = mid + 1
        }
        return res
    }