Skip to main content
CodePeetCodePeet
CodePeet 250

Koko Eating Bananas

MEDIUMProblemSolveExternal Links

Description

Koko loves eating bananas. She has n piles of bananas in front of her, where the i-th pile contains piles[i] bananas. The guards have left and will return in h hours.

Koko eats at a constant speed of k bananas per hour. Each hour, she picks one pile and eats up to k bananas from it. If a pile has fewer than k bananas, she eats all the remaining bananas in that pile and waits out the rest of that hour doing nothing — she does not move to another pile within the same hour.

Koko wants to eat as slowly as possible while still finishing all the bananas before the guards return. Your task is to find the minimum integer value of k (bananas per hour) such that Koko can eat all the bananas within h hours.

Examples

Example 1

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

Output: 4

Explanation: At speed k = 4 bananas/hour:

  • Pile of 3: needs ⌈3/4⌉ = 1 hour
  • Pile of 6: needs ⌈6/4⌉ = 2 hours
  • Pile of 7: needs ⌈7/4⌉ = 2 hours
  • Pile of 11: needs ⌈11/4⌉ = 3 hours
  • Total = 1 + 2 + 2 + 3 = 8 hours, exactly meeting the deadline.

At speed k = 3, total hours = 1 + 2 + 3 + 4 = 10 > 8, which exceeds the limit. So 4 is the minimum valid speed.

Example 2

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

Output: 30

Explanation: With 5 piles and only 5 hours, Koko must finish each pile in exactly 1 hour. The largest pile has 30 bananas, so she needs to eat at speed 30 to clear every pile within a single hour each.

Example 3

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

Output: 23

Explanation: At speed k = 23:

  • Pile of 30: needs ⌈30/23⌉ = 2 hours
  • Pile of 11: needs ⌈11/23⌉ = 1 hour
  • Pile of 23: needs ⌈23/23⌉ = 1 hour
  • Pile of 4: needs ⌈4/23⌉ = 1 hour
  • Pile of 20: needs ⌈20/23⌉ = 1 hour
  • Total = 2 + 1 + 1 + 1 + 1 = 6 hours, exactly within the limit.

At k = 22, the pile of 30 takes ⌈30/22⌉ = 2 hours, and the pile of 23 takes ⌈23/22⌉ = 2 hours, giving total = 2 + 1 + 2 + 1 + 1 = 7 > 6. So 23 is the minimum.

Constraints

  • 1 ≤ piles.length ≤ 10^4
  • piles.length ≤ h ≤ 10^9
  • 1 ≤ piles[i] ≤ 10^9

Editorial

Brute Force

Intuition

The simplest way to find the minimum eating speed is to try every possible speed starting from the slowest (k = 1) and check if Koko can finish all bananas within h hours at that speed. The first speed that works is our answer.

For any given speed k, we can calculate how many hours Koko needs for each pile: she needs ⌈piles[i] / k⌉ hours for pile i (ceiling division, because even a partial hour of eating still uses up a full hour). If the total hours across all piles is at most h, then speed k is sufficient.

So we start at k = 1, compute the total hours, and if it exceeds h, we try k = 2, then k = 3, and so on. The maximum useful speed is the size of the largest pile — eating faster than that gives no benefit since Koko can only eat from one pile per hour anyway.

Step-by-Step Explanation

Let's trace through with piles = [3, 6, 7, 11], h = 8:

Step 1: Try k = 1.

  • Hours per pile: ⌈3/1⌉ + ⌈6/1⌉ + ⌈7/1⌉ + ⌈11/1⌉ = 3 + 6 + 7 + 11 = 27
  • 27 > 8 → Too slow.

Step 2: Try k = 2.

  • Hours: ⌈3/2⌉ + ⌈6/2⌉ + ⌈7/2⌉ + ⌈11/2⌉ = 2 + 3 + 4 + 6 = 15
  • 15 > 8 → Still too slow.

Step 3: Try k = 3.

  • Hours: ⌈3/3⌉ + ⌈6/3⌉ + ⌈7/3⌉ + ⌈11/3⌉ = 1 + 2 + 3 + 4 = 10
  • 10 > 8 → Still too slow.

Step 4: Try k = 4.

  • Hours: ⌈3/4⌉ + ⌈6/4⌉ + ⌈7/4⌉ + ⌈11/4⌉ = 1 + 2 + 2 + 3 = 8
  • 8 ≤ 8 → This works! Koko can finish in exactly 8 hours.

Result: Minimum speed k = 4.

Brute Force — Testing Speeds 1, 2, 3, 4 Sequentially — Watch how we test each speed from k=1 upward, computing total hours for all piles, until we find the first speed that fits within h hours.

Algorithm

  1. Compute max_pile = the maximum value in piles. This is the upper bound for k.
  2. For k = 1 to max_pile:
    a. Compute total hours needed: sum of ⌈piles[i] / k⌉ for all piles.
    b. If total hours ≤ h, return k.
  3. Return max_pile (guaranteed to work since h ≥ piles.length).

Code

#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int maxPile = *max_element(piles.begin(), piles.end());
        
        for (int k = 1; k <= maxPile; k++) {
            long long totalHours = 0;
            for (int pile : piles) {
                totalHours += (pile + k - 1) / k;
            }
            if (totalHours <= h) {
                return k;
            }
        }
        
        return maxPile;
    }
};
import math

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        max_pile = max(piles)
        
        for k in range(1, max_pile + 1):
            total_hours = sum(math.ceil(pile / k) for pile in piles)
            if total_hours <= h:
                return k
        
        return max_pile
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int maxPile = 0;
        for (int pile : piles) {
            maxPile = Math.max(maxPile, pile);
        }
        
        for (int k = 1; k <= maxPile; k++) {
            long totalHours = 0;
            for (int pile : piles) {
                totalHours += (pile + k - 1) / k;
            }
            if (totalHours <= h) {
                return k;
            }
        }
        
        return maxPile;
    }
}

Complexity Analysis

Time Complexity: O(max(piles) × n)

In the worst case, we try every speed from 1 to max(piles). For each speed, we iterate through all n piles to compute total hours. If max(piles) is M, this gives O(M × n). With M up to 10^9 and n up to 10^4, this can be up to 10^13 operations — far too slow.

Space Complexity: O(1)

We only use a few variables (k, totalHours, maxPile). No additional data structures that grow with input size.

Why This Approach Is Not Efficient

The brute force tries every possible speed from 1 to max(piles), which can be up to 10^9. For each candidate speed, it scans all n piles. This results in O(max(piles) × n) time, which can reach 10^13 operations — unacceptable for any reasonable time limit.

The critical observation that enables a better approach is the monotonic property of the feasibility check. If speed k is fast enough for Koko to finish in time, then every speed greater than k is also fast enough. Conversely, if speed k is too slow, every speed less than k is also too slow. This means the feasibility results form a pattern like:

Speed:     1    2    3    4    5    6   ...   11
Feasible:  No   No   No   Yes  Yes  Yes ...  Yes

We need to find the leftmost 'Yes' — the exact boundary where 'No' turns to 'Yes'. This is the classic scenario for binary search, which can find this boundary in O(log M) checks instead of O(M) checks.

Instead of testing speeds one by one, binary search lets us halve the search space with each check, reducing the number of feasibility checks from up to 10^9 down to about 30 (since log₂(10^9) ≈ 30).

Optimal Approach - Binary Search on Answer

Intuition

Think of it this way: instead of testing speeds 1, 2, 3, 4, ... one by one, what if you could jump to the middle of the range and ask "is this speed enough?" Based on the answer, you eliminate half of all remaining possibilities.

Imagine a number line from 1 to max(piles). Somewhere on this line is a magical boundary point. Every speed to the left of it is too slow, and every speed at or to the right of it is fast enough. We want to find that exact boundary.

Binary search does exactly this. We maintain a range [left, right] and repeatedly test the midpoint:

  • If the midpoint speed is fast enough → the answer is at or below the midpoint. Narrow the search to [left, mid].
  • If the midpoint speed is too slow → the answer is above the midpoint. Narrow the search to [mid + 1, right].

Each step cuts the search space in half. Starting with a range of up to 10^9, we need at most ~30 steps to find the exact answer.

The helper function canFinish(k) computes whether speed k is sufficient: for each pile, compute ⌈pile/k⌉ (hours needed), sum them up, and check if the total is ≤ h. This function runs in O(n) time per call.

Step-by-Step Explanation

Let's trace through with piles = [3, 6, 7, 11], h = 8:

Search range: [1, 11] (1 to max(piles))

Step 1: left = 1, right = 11, mid = (1 + 11) / 2 = 6

  • canFinish(6): ⌈3/6⌉ + ⌈6/6⌉ + ⌈7/6⌉ + ⌈11/6⌉ = 1 + 1 + 2 + 2 = 6
  • 6 ≤ 8? Yes → Speed 6 works. But maybe we can go slower. Search left: right = 6.

Step 2: left = 1, right = 6, mid = (1 + 6) / 2 = 3

  • canFinish(3): ⌈3/3⌉ + ⌈6/3⌉ + ⌈7/3⌉ + ⌈11/3⌉ = 1 + 2 + 3 + 4 = 10
  • 10 ≤ 8? No → Speed 3 is too slow. Search right: left = 4.

Step 3: left = 4, right = 6, mid = (4 + 6) / 2 = 5

  • canFinish(5): ⌈3/5⌉ + ⌈6/5⌉ + ⌈7/5⌉ + ⌈11/5⌉ = 1 + 2 + 2 + 3 = 8
  • 8 ≤ 8? Yes → Speed 5 works. Try slower: right = 5.

Step 4: left = 4, right = 5, mid = (4 + 5) / 2 = 4

  • canFinish(4): ⌈3/4⌉ + ⌈6/4⌉ + ⌈7/4⌉ + ⌈11/4⌉ = 1 + 2 + 2 + 3 = 8
  • 8 ≤ 8? Yes → Speed 4 works. Try slower: right = 4.

Step 5: left = 4, right = 4, mid = 4

  • canFinish(4): total = 8 ≤ 8? Yes → right = 4.

Step 6: left = 4, right = 3 → left > right. Loop ends.

Result: The answer is 4. We found it in ~5 binary search steps instead of testing 4 speeds linearly.

Binary Search on Eating Speed — Halving the Search Range — Watch how binary search narrows the range of possible speeds by half at each step, quickly converging on the minimum feasible speed k=4.

Algorithm

  1. Set the binary search boundaries: left = 1, right = max(piles).
  2. While left ≤ right:
    a. Compute mid = (left + right) / 2.
    b. Check if Koko can finish at speed mid: sum ⌈piles[i]/mid⌉ for all i.
    c. If total ≤ h (feasible): record mid as a candidate, set right = mid - 1 (try slower).
    d. Else (not feasible): set left = mid + 1 (need faster).
  3. Return the best candidate found.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1;
        int right = *max_element(piles.begin(), piles.end());
        int result = right;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // Check if Koko can finish at speed mid
            long long totalHours = 0;
            for (int pile : piles) {
                totalHours += (long long)(pile + mid - 1) / mid;
            }
            
            if (totalHours <= h) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
};
import math

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        left, right = 1, max(piles)
        result = right
        
        while left <= right:
            mid = (left + right) // 2
            
            # Check if Koko can finish at speed mid
            total_hours = sum(math.ceil(pile / mid) for pile in piles)
            
            if total_hours <= h:
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return result
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }
        int result = right;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // Check if Koko can finish at speed mid
            long totalHours = 0;
            for (int pile : piles) {
                totalHours += (pile + mid - 1) / mid;
            }
            
            if (totalHours <= h) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × log(max(piles)))

The binary search runs for O(log M) iterations, where M = max(piles). In each iteration, the feasibility check scans all n piles in O(n). This gives O(n × log M) total. With M up to 10^9, log₂(10^9) ≈ 30, so we perform roughly 30 × n operations. For n = 10^4, that is about 3 × 10^5 operations — extremely fast.

Space Complexity: O(1)

We only use a constant number of variables: left, right, mid, totalHours, and result. No additional data structures are needed.