Data Structures & Algorithms (Binary Search): Koko Eating Bananas

February 17, 2026

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.

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

Playground: Leetcode 875

Basic Intuition

To eat pile[i] bananas at a rate of k bananas per hour, koko will take ceil(pile[i] / k) hours.

basic-intuition

Start exploring k from 1. For each k, iterate over every pile and calculate the cumulative hours required to eat all the bananas using ceil(pile / k). Return the first k for which the cumulative hours are less than or equal to h, as it is the minimum valid eating speed.

Algorithm

1. Initialize "k" to 1.
2. Repeat the following steps until we have an eligible "k".
    3. Initialize a variable, "cumHrs" to 0, to store the cumulative hours required to eat
       all piles at the rate of "k" bananas per hour.
    4. Iterate over each pile and add "ceil(pile / k)" to "cumHrs".
    5. If the "cumHrs" is less than or equal to "h", return "k".
    6. Otherwise, increment "k" by 1.

Implementation

Sample inputs
1public int minEatingSpeed(int[] piles, int h) {
2
3 // 1. Initialize "k" to 1.
4 int k = 1;
5
6 // 2. Repeat the following steps until we have an eligible "k".
7 while (true) {
8
9 // 3. Initialize a variable, "cumHrs" to 0, to store the cumulative hours required to eat
10 // all piles at the rate of "k" bananas per hour.
11 double cumHrs = 0;
12
13 // 4. Iterate over each pile and add "ceil(pile / k)" to "cumHrs".
14 for (int pile : piles) {
15 cumHrs += Math.ceil((double) pile / k);
16 }
17
18 // 5. If the "cumHrs" is less than or equal to "h", return "k".
19 if (cumHrs <= h) {
20 return k;
21 }
22
23 // 6. Otherwise, increment "k" by 1.
24 k++;
25
26 }
27
28}
Eating speed
k = —
Hour limit
h = 8
piles
3—
6—
7—
11—
0
1
2
3
ceil(pile / k)
cumHrs —h 8
The mark is the hour limit h.
k = —
cumHrs = —
h = 8
pile = —
Returned k
—
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/33

Time Complexity

For each iteration, we only perform basic arithmetic operations and validation checks, each taking constant time, O(1). Therefore, the time complexity primarily depends on the number of iterations.

In the worst case, i.e., when h = n, where n = piles.length, the outer loop runs for max(piles) times. For each iteration, the inner loop traverses all n times.

Since the total iterations is max(piles) x n, the overall time complexity is O(max(piles) x n).

Space Complexity

We use only a variable, cumHrs, to store the cumulative hours required to eat all piles at a rate of k. Since no additional data structures are used, the overall space complexity is O(1).

Key Observations

When k >= max(piles), Koko can finish each pile in 1 hour. Therefore, she needs a minimum of piles.length hours to eat all the piles. For example, if piles = [3, 6, 7, 11], then for any k >= 11, Koko can finish each pile in 1 hour, requiring a total of 4 hours to eat all the piles.

Hence, we only need to search within the range [1, max(piles)] to find the minimum rate k that allows Koko to eat all the bananas within h hours.

key-observation-1

The search space [1, max(piles)] follows a monotonic pattern: as the eating speed (k) increases, the total hours required (cumHrs) to finish all the piles will strictly decrease or stay the same (never increase).

Because of this:

  • If a speed is too slow (cumHrs > h), we can eliminate that speed and all smaller speeds.

binary-search-1

  • If a speed is sufficient (cumHrs <= h), we can eliminate all larger speeds because we're searching for the minimum valid speed.

binary-search-2

These observations allow us to use binary search to halve the search space in each iteration until we find the minimum valid eating speed.

Algorithm

1. Initialize:
    a. Two pointers, "left = 1" and "right = max(piles)", to define the boundaries of 
       the search space.
    b. A variable, "minimumSpeed = max(piles)" to track the minimum eating speed found 
       so far.

2. Repeat while the search space is not empty ("left" <= "right"):
    3. Calulate the "middle" element in the current search space.
    4. Initialize a variable, "totalHours = 0" to track the hours required to eat
       all piles at speed "middle".
    5. Iterate over each pile and add "ceil(pile / middle)" to "totalHours".
    6. If "totalHours" > "h", "middle" is too slow. Move "left" to "middle + 1" to 
       eliminate "middle" and all smaller speeds.
    7. Otherwise, "middle" is a valid candidate. Update "minimumSpeed" to
       "middle" and move "right" to "middle - 1" to search for a smaller valid speed.

8. Return "minimumSpeed".

Implementation

Sample inputs
1public int minEatingSpeed(int[] piles, int h) {
2
3 /* 1. Initialize:
4 * a. Two pointers to define the boundaries of the search space.
5 * b. A variable to track the minimum eating speed found so far.
6 */
7 int left = 1, right = Arrays.stream(piles).max().getAsInt();
8 int minimumSpeed = 0;
9
10 //2. Repeat while the search space is not empty.
11 while (left <= right) {
12
13 // 3. Calulate the middle element.
14 int middle = (left + right) / 2;
15
16 // 4. Track the total hours required at the current speed.
17 double totalHours = 0;
18
19 // 5. Iterate over each pile.
20 for (int pile : piles) {
21 // Add [pile / middle] to the total required hours.
22 totalHours += Math.ceil((double) pile / middle);
23 }
24
25 // 6. If the speed is too slow, eliminate it and smaller speeds.
26 if (totalHours > h) {
27 left = middle + 1;
28
29 // 7. Otherwise, update the minimum speed and search for a smaller one.
30 } else {
31 minimumSpeed = middle;
32 right = middle - 1;
33 }
34
35 }
36
37
38 // 8. Return the minimum valid eating speed.
39 return minimumSpeed;
40
41}
Current middle
middle = —
Hour limit
h = 8
search space over k[1, 11]
1max(piles) = 11
candidate speedseliminatedminimumSpeed
piles
3—
6—
7—
11—
0
1
2
3
ceil(pile / middle)
totalHours —h 8
The mark is the hour limit h.
left = —
middle = —
right = —
totalHours = —
minimumSpeed
—
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/32

Time Complexity

The binary search takes O(logm) iterations, where m = maximum number of bananas in any pile. In each iteration, we traverse all n piles to calculate the total hours required. Each calculation takes O(1) time, so each iteration takes O(n) time.

Therefore, the overall time complexity is O(n x logm).

Space Complexity

We use only a fixed number of variables, such as left, right, middle, minimumSpeed, and totalHours. Since we don't use any additional data structures that grow with input size, the overall space complexity is O(1).