We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Koko Eating Bananas

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem can be solved using binary search to find the optimal eating speed k.
  • The maximum speed k cannot be more than the largest pile of bananas.
  • The minimum speed k starts from 1, since Koko has to eat at least one banana.
  • For a given k, we can calculate how many hours it would take Koko to finish all piles.
  • We need to find the smallest k such that the total hours taken is less than or equal to h.

Space and Time Complexity

Time Complexity: O(n log(max(piles)))
Space Complexity: O(1)

Solution

To solve the problem, we will use a binary search approach. The idea is to determine the minimum speed k that allows Koko to finish eating all the bananas in h hours.

  1. Set the left boundary of k to 1 and the right boundary to the maximum number of bananas in any pile.
  2. While the left boundary is less than or equal to the right boundary:
    • Calculate the mid-point (k) as the average of the left and right boundaries.
    • Calculate the total hours needed to eat all bananas at this speed k.
    • If the total hours are less than or equal to h, it means Koko can eat at this speed or slower, so we move the right boundary down to search for a smaller k.
    • If the total hours exceed h, it means k is too small, so we move the left boundary up.
  3. The process continues until we narrow down to the minimum valid k.

Code Solutions

def minEatingSpeed(piles, h):
    def canFinish(k):
        hours = 0
        for pile in piles:
            hours += (pile + k - 1) // k  # Equivalent to ceil(pile / k)
        return hours <= h

    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if canFinish(mid):
            right = mid  # Try for a smaller k
        else:
            left = mid + 1  # Increase k
    return left
← Back to All Questions