Koko Eating Bananas

Med

#0829Time: O(M * N), where N is the number of piles and M is the maximum possible eating speed (the value of the largest pile). In the worst case, we might have to check all speeds from 1 to M. For each speed, we iterate through N piles. This is too slow for the given constraints.Space: O(1), as we only use a constant amount of extra space for variables.23 companies

Algorithms

Binary Search

Data structures

Array

Companies

Accenture Atlassian Deutsche Bank DoorDash

Prompt

Koko loves to eat bananas. There are n piles of bananas, the i^th 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

Constraints:

1 <= piles.length <= 10⁴
piles.length <= h <= 10⁹
1 <= piles[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible eating speed k starting from 1. For each speed, we calculate the total time required to eat all the bananas. The first speed k that allows Koko to finish within h hours is the minimum possible speed and is returned as the answer. This method is straightforward but inefficient.

Algorithm

Iterate through possible eating speeds k starting from 1 up to a reasonable upper bound (like the maximum pile size).
For each speed k, calculate the total hours totalHours required to eat all bananas.
To calculate totalHours, iterate through each pile p in piles.
The time for one pile is ceil((double)p / k), which can be calculated using integer arithmetic as (p + k - 1) / k.
Sum up the hours for all piles.
If totalHours is less than or equal to the given h, then k is the minimum speed. Return k immediately.

Walkthrough

The brute-force solution systematically tests each possible value for the eating speed k, beginning with the slowest possible speed, k=1. For a given k, we can determine the total time required by summing up the hours needed for each pile. The hours to finish a pile of p bananas with speed k is ceil(p / k). In integer arithmetic, this is (p + k - 1) / k. We calculate this for all piles and sum them up. If the total time is within the allowed h hours, we have found our answer, as we are checking k in increasing order. The search for k can stop once we reach the size of the largest pile, as any speed greater than that won't reduce the time for that pile (it will still take 1 hour).

1class Solution {2    public int minEatingSpeed(int[] piles, int h) {3        // The maximum possible speed to check is the largest pile size.4        int maxPile = 0;5        for (int pile : piles) {6            maxPile = Math.max(maxPile, pile);7        }8 9        // Start checking speeds from k = 1.10        for (int k = 1; k <= maxPile; k++) {11            long totalHours = 0;12            // Calculate total hours for the current speed k.13            for (int pile : piles) {14                totalHours += (pile + k - 1) / k;15            }16            // If Koko can finish within h hours, this is the minimum k.17            if (totalHours <= h) {18                return k;19            }20        }21        return -1; // Should not be reached given the problem constraints.22    }23}

Complexity

Time

O(M * N), where N is the number of piles and M is the maximum possible eating speed (the value of the largest pile). In the worst case, we might have to check all speeds from 1 to M. For each speed, we iterate through N piles. This is too slow for the given constraints.

Space

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

Pros

Simple to understand and implement.
Guaranteed to find the correct solution if it runs to completion.

Cons

Extremely inefficient due to the large search space for k.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints, as the maximum pile size can be up to 10^9.

A much more efficient approach utilizes binary search on the possible range of eating speeds k. The key observation is that the time taken to eat all bananas is a monotonically decreasing function of the speed k. That is, if Koko can finish with speed k, she can also finish with any speed greater than k. This property allows us to efficiently discard half of the search space in each step, leading to a logarithmic time complexity for the search.

Algorithm

Determine the search range for the speed k. The lower bound low is 1. The upper bound high is the maximum number of bananas in any single pile.
Perform a binary search within the range [low, high].
In each step, calculate the middle speed mid = low + (high - low) / 2.
Check if it's possible to finish all bananas with speed mid within h hours.
To do this, calculate the total hours required for speed mid. Initialize totalHours = 0 (as a long to prevent overflow). Iterate through each pile p and add (p + mid - 1) / mid to totalHours.
If the calculated totalHours is less than or equal to h, it means mid is a possible answer. We store it and try to find a smaller valid speed by searching in the left half: high = mid - 1.
If totalHours is greater than h, mid is too slow. We need to increase the speed by searching in the right half: low = mid + 1.
The loop continues until low > high. The last valid speed recorded is the minimum one.

Walkthrough

The problem asks for the minimum k that satisfies a condition. The condition (finishing within h hours) has a monotonic property with respect to k: if a speed k works, any speed k' > k also works. This structure is a perfect fit for binary search on the answer.

The search space for k ranges from a minimum of 1 to a maximum of the largest pile size. Any speed higher than the largest pile is redundant. We can set low = 1 and high = max(piles).

We then apply binary search:

Pick a mid speed from the current range [low, high].
Calculate the total hours needed to eat all bananas at this mid speed. It's crucial to use a long for the total hours to avoid overflow, as the sum can exceed the capacity of a 32-bit integer.
If the total hours is less than or equal to h, mid is a valid speed. We store it as a potential answer and try to find an even smaller speed by narrowing our search to the left half (high = mid - 1).
If the total hours exceeds h, the speed mid is too slow. We must increase the speed, so we search in the right half (low = mid + 1).

This process continues until the search space is exhausted (low > high), and the best answer found will be the minimum possible speed k.

1class Solution {2    public int minEatingSpeed(int[] piles, int h) {3        int low = 1;4        int high = 0;5        for (int pile : piles) {6            high = Math.max(high, pile);7        }8 9        int minSpeed = high;10 11        while (low <= high) {12            int mid = low + (high - low) / 2;13            if (canFinish(piles, h, mid)) {14                minSpeed = mid;15                high = mid - 1; // Try for a smaller speed16            } else {17                low = mid + 1; // Speed is too slow, need to increase it18            }19        }20        return minSpeed;21    }22 23    private boolean canFinish(int[] piles, int h, int k) {24        long totalHours = 0;25        for (int pile : piles) {26            // Calculate hours for the current pile and add to total.27            // (pile + k - 1) / k is equivalent to Math.ceil((double)pile / k)28            totalHours += (long)(pile + k - 1) / k;29        }30        return totalHours <= h;31    }32}

Complexity

Time

O(N * log M), where N is the number of piles and M is the maximum value in `piles`. The binary search on the range of speeds takes `log M` iterations. In each iteration, we iterate through all N piles to calculate the total time, which takes O(N) time.

Space

O(1), as we only use a few variables to manage the binary search state, not counting the input array.

Trade-offs

Pros

Highly efficient and passes all test cases within the time limit.
Optimal solution for this type of problem (searching for a minimum/maximum value that satisfies a monotonic condition).

Cons

Slightly more complex to conceptualize than a linear search.
Requires careful handling of potential integer overflow when calculating the total hours, which must be stored in a long.

Solutions

Solution

1public class Solution {2    public int MinEatingSpeed(int[] piles, int h) {3        int left = 1, right = piles.Max();4        while (left < right) {5            int mid = (left + right) >> 1;6            int s = 0;7            foreach(int pile in piles) {8                s += (pile + mid - 1) / mid;9            }10            if (s <= h) {11                right = mid;12            } else {13                left = mid + 1;14            }15        }16        return left;17    }18}

1class Solution { public int minEatingSpeed ( int [] piles , int h ) { int left = 1 , right = ( int ) 1 e9 ; while ( left < right ) { int mid = ( left + right ) >>> 1 ; int s = 0 ; for ( int x : piles ) { s += ( x + mid - 1 ) / mid ; } if ( s <= h ) { right = mid ; } else { left = mid + 1 ; } } return left ; } }

1class Solution { public: int minEatingSpeed ( vector < int >& piles , int h ) { int left = 1 , right = 1e9 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; int s = 0 ; for ( int & x : piles ) s += ( x + mid - 1 ) / mid ; if ( s <= h ) right = mid ; else left = mid + 1 ; } return left ; } };

1class Solution : def minEatingSpeed ( self , piles : List [ int ], h : int ) -> int : left , right = 1 , int ( 1e9 ) while left < right : mid = ( left + right ) >> 1 s = sum (( x + mid - 1 ) // mid for x in piles ) if s <= h : right = mid else : left = mid + 1 return left

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem