MediumCoding

Koko eating bananas.

Asked at

Flipkart

Amazon

Flexport

Goldman Sachs

Nvidia

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

A monkey is given n piles of bananas, where the 'ith' pile has nums[i] bananas. An integer h represents the total time in hours to eat all the bananas.

Each hour, the monkey chooses a non-empty pile of bananas and eats k bananas. If the pile contains fewer than k bananas, the monkey eats all the bananas in that pile and does not consume any more bananas in that hour.

Determine the minimum number of bananas the monkey must eat per hour to finish all the bananas within h hours.

Input: n = 4, nums = [7, 15, 6, 3], h = 8 Output: 5 Explanation: If Koko eats 5 bananas/hr, he will take 2, 3, 2, and 1 hour to eat the piles accordingly. So, he will take 8 hours to complete all the piles.

Input: n = 5, nums = [25, 12, 8, 14, 19], h = 5 Output: 25 Explanation: If Koko eats 25 bananas/hr, he will take 1, 1, 1, 1, and 1 hour to eat the piles accordingly. So, he will take 5 hours to complete all the piles.

Input: n = 4, nums = [3, 7, 6, 11], h = 8

1 <= n <= 104
n <= h <= 109
1 <= nums[i] <= 109

cpp

class Solution {
public:
int minimumRateToEatBananas(vector<int> nums, int h) {
 
    }
};

java

class Solution {
    public int minimumRateToEatBananas(int[] nums, int h) {
   
    }
}

python

class Solution:
    def minimumRateToEatBananas(self, nums, h):

javascript

class Solution {
    minimumRateToEatBananas(nums, h) {
  
    }
}

csharp

class Solution
{
    public int MinimumRateToEatBananas(List<int> nums, int h)
    {
       
    }
}

func minimumRateToEatBananas(nums []int, h int) int {
  
}

Stuck? Show a way to structure it+

01Search possible speeds from 1 to the largest pile.
02For a speed, sum ceil(pile/speed) hours.
03If total hours fit, retain the speed and search lower.
04Otherwise search higher.

Reference answer

The predicate canFinish(k) is monotonic: if speed k works, any larger speed works too. Binary-search k in [1, maxPile]; calculate required hours as (pile + k - 1) / k using a wide integer and stop early once it exceeds h. Keep the smallest feasible speed. This costs O(n log maxPile) time and O(1) extra space. Never use floating point for ceiling division or initialize the lower bound to zero. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

Why is feasibility monotonic here?
Tests: proof
How would weighted eating costs alter the predicate?
Tests: modeling

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question