Leetcode - 875. Koko Eating Bananas

Medium

Dec 22, 2025

#binary-search

#math

875. Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

1 <= piles.length <= 104
piles.length <= h <= 109
1 <= piles[i] <= 109

Constraints:

Notes

Intuition

The eating speed ranges from 1 to max(piles). Binary search finds the minimum speed that lets Koko finish in time. Higher speeds always work if lower speeds work, so we're finding a threshold.

Implementation

Binary search on speed from 1 to max(piles). For each candidate speed, calculate total hours needed (sum of ceil(pile/speed) for each pile). If hours exceed h, we need more speed—search right. Otherwise, search left for potentially slower valid speeds. When the loop exits, l is the minimum valid speed.

Edge-cases

Use ceiling division because even one banana in a pile takes a full hour. The answer is l at the end, not r.

Time: O(n log m) — where m is max(piles), binary search with O(n) validation
Space: O(1) — only tracking pointers

Complexity

Solution

from typing import List
import math

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)

        while l <= r:
            speed = (l + r) // 2
            # calculating hours for this speed
            hours = 0
            for pile in piles:
                hours += math.ceil(pile/speed)

            if hours > h: # increase speed
                l = speed + 1
            else: # decrease speed
                r = speed - 1

        return l
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()