LeetCode Entry

875. Koko Eating Bananas

08.03.2023 medium 2023 kotlin

For more robust binary search

875. Koko Eating Bananas medium

blog post

fun minEatingSpeed(piles: IntArray, h: Int): Int {
    fun canEatAll(speed: Long): Boolean {
        var time = 0L
        piles.forEach {
            time += (it.toLong() / speed) + if ((it.toLong() % speed) == 0L) 0L else 1L
        }
        return time <= h
    }
    var lo = 1L
    var hi = piles.asSequence().map { it.toLong() }.sum()!!
    var minSpeed = hi
    while (lo <= hi) {
        val speed = lo + (hi - lo) / 2
        if (canEatAll(speed)) {
            minSpeed = minOf(minSpeed, speed)
            hi = speed - 1
        } else {
            lo = speed + 1
        }
    }
    return minSpeed.toInt()
}

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/142

Intuition

Given the speed we can count how many hours take Coco to eat all the bananas. With growth of speed hours growth too, so we can binary search in that space.

Approach

For more robust binary search:

• use inclusive condition check lo == hi
• always move boundaries mid + 1, mid - 1
• compute the result on each step

  Complexity

• Time complexity: \(O(nlog_2(m))\), m - is hours range
• Space complexity: \(O(1)\)