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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Koko Eating Bananas

Number: 907

Difficulty: Medium

Paid? No

Companies: Amazon, DoorDash, Google, Meta, Bloomberg, Microsoft, Turing, TikTok, Uber, Salesforce, Flipkart, oyo, LinkedIn, Netflix, DE Shaw, Accenture, PhonePe, Infosys, Citadel, VMware, Adobe, Apple, Yahoo, Deutsche Bank, Splunk, Oracle, Walmart Labs

Problem Description

Koko loves to eat bananas and has n piles of bananas where piles[i] is the number of bananas in the iᵗʰ pile. With the guards returning in h hours, Koko chooses a constant eating rate k bananas per hour. Each hour, she picks a pile and eats k bananas or the remaining bananas if the pile has less than k. The task is to find the minimum integer k such that Koko can finish all bananas within h hours.

Key Insights

  • The required eating speed k lies in the range [1, max(piles)].
  • For a given k, one can calculate the total hours needed by summing up ceil(pile / k) for each pile.
  • The problem can be solved efficiently using binary search to find the minimum k that satisfies the time constraint.
  • Early termination in the hour calculation can be used if the computed hours exceed h.

Space and Time Complexity

Time Complexity: O(n log(max(pile))) where n is the number of piles and max(pile) is the maximum bananas in a pile. Space Complexity: O(1) extra space beyond the input.

Solution

We use binary search on the candidate eating rate k. The search space starts at 1 (minimum possible speed) and goes up to the maximum number of bananas in any pile. For each candidate k, we simulate the number of hours Koko would take by calculating hours += (pile + k - 1) // k for each pile (this formula performs the ceiling division). If the total hours are less than or equal to h, then k might be a valid solution and we try to lower it; otherwise, we increase k. The binary search continues until we converge on the minimum valid eating speed.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with line-by-line comments.

def minEatingSpeed(piles, h):
    # Helper function to determine if Koko can finish with speed k
    def canFinish(k):
        hours = 0
        for pile in piles:
            # Calculate hours by using ceiling division for each pile
            hours += (pile + k - 1) // k
        return hours <= h

    left, right = 1, max(piles)  # Speed is between 1 and the max pile element
    while left < right:
        mid = (left + right) // 2  # Candidate eating speed
        if canFinish(mid):
            right = mid  # Try finding a smaller valid speed
        else:
            left = mid + 1  # Increase the speed because mid is too slow
    return left

# Example usage:
piles = [3, 6, 7, 11]
h = 8
print(minEatingSpeed(piles, h))  # Expected output: 4
← Back to All Questions