How do you solve Koko Eating Bananas?

Use binary search between 1 and max(piles). For each mid speed k, compute total hours by summing ceil(pile/k) for all piles. If total hours <= h, update result and search left half to find smaller feasible speeds. Otherwise, search right half. Return the smallest k found.

Koko Eating Bananas

Q: What is the time complexity of Koko Eating Bananas?

O(n log m). Where n is the number of piles and m is the maximum pile size. Each binary search iteration takes O(n) to compute total hours, and binary search performs O(log m) iterations.

Q: What pattern does Koko Eating Bananas use?

The Pattern: Binary Search (Search Space Reduction on Monotonic Function) The Heuristic: When the problem asks for a minimum or maximum value satisfying a monotonic condition, transform the problem into a decision problem and use binary search over the value domain to efficiently find the optimal solution.

Medium Modified Binary Search

Problem

Given an array piles where piles[i] is the number of bananas in the ith pile and an integer h representing hours, return the minimum integer k such that Koko can eat all bananas within h hours by eating k bananas per hour from one pile at a time.

1 ≤ piles.length ≤ 10⁴
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹

Example

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

Output: 4

At speed k=4, Koko eats as follows: - Hour 1: Eat 4 bananas from pile 1 (3 bananas), finishes pile 1 in 1 hour. - Hour 2: Eat 4 bananas from pile 2 (6 bananas), 2 hours total. - Hour 3: Eat remaining 2 bananas from pile 2, 3 hours total. - Hour 4: Eat 4 bananas from pile 3 (7 bananas), 4 hours total. - Hour 5: Eat remaining 3 bananas from pile 3, 5 hours total. - Hour 6: Eat 4 bananas from pile 4 (11 bananas), 6 hours total. - Hour 7: Eat 4 bananas from pile 4, 7 hours total. - Hour 8: Eat remaining 3 bananas from pile 4, 8 hours total. This is the minimum speed to finish within 8 hours.

Approach

Straightforward Solution

A brute-force approach tries all speeds from 1 to max(piles), computing hours needed for each. This is O(n * max(piles)) and is infeasible for large inputs due to the large search space.

Core Observation

The minimum eating speed k lies between 1 and the maximum pile size. For any candidate speed k, the total hours needed to finish all piles can be computed by summing the ceiling of pile size divided by k. This total hours function is monotonically decreasing with respect to k.

Path to Optimal

Recognizing the monotonic relationship between speed and hours needed enables binary search on k. By checking midpoints and adjusting the search space based on whether the total hours exceed h, the algorithm efficiently narrows down the minimum feasible speed.

Optimal Approach

Preview

Use binary search between 1 and max(piles). For each mid speed k, compute total hours by summing ceil(pile/k) for all piles…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log m)

Where n is the number of piles and m is the maximum pile size. Each binary search iteration takes O(n) to compute total hours, and binary search performs O(log m) iterations.

Space

O(1)

Only a few variables are used for pointers and counters; no additional data structures scale with input size.

Pattern Spotlight

Binary Search (Search Space Reduction on Monotonic Function)

When the problem asks for a minimum or maximum value satisfying a monotonic condition, transform the problem into a decision problem and use binary search over the value domain to efficiently find the optimal solution.

Solution

Python

1import math
2
3class Solution:
  def minEatingSpeed(self, piles: list[int], h: int) -> int:
      left, right = 1, max(piles)
      res = right
7
      while left <= right:
          k = (left + right) // 2
          hours = 0
          for p in piles:
              hours += math.ceil(p / k)
          
          if hours <= h:
              res = min(res, k)
              right = k - 1
          else:
              left = k + 1
      
      return res

Step-by-Step Solution

Initialize Binary Search Boundaries and Result

5left, right = 1, max(piles)
6res = right

Objective

To set the initial search space for the eating speed between 1 and the largest pile size, and initialize the result to the upper bound.

Key Insight

The minimum speed cannot be less than 1 and cannot exceed the largest pile size, as eating faster than the largest pile is unnecessary. Initializing the result to the upper bound ensures a valid starting point for minimization.

Interview Quick-Check

Core Logic

Setting left to 1 and right to max(piles) defines the search space for the binary search over possible speeds.

State & Boundaries

Initializing result to right ensures that if no smaller speed satisfies the condition, the maximum pile size is returned.

Perform Binary Search to Find Minimum Feasible Speed

To iteratively narrow down the search space by checking the feasibility of the mid speed and adjusting boundaries accordingly.

Return the Minimum Eating Speed Found

To output the smallest speed k that allows Koko to finish eating within h hours.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 12 Critical

hours += math.ceil(p / k)

Add the ceiling of pile divided by k to the total hours.

This line is critical because it correctly models the time cost per pile using ceiling division, which is essential for accurate feasibility checks; using floor division would underestimate hours and break correctness.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why is binary search applicable to the eating speed k in this problem?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Koko Eating Bananas from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Koko Eating Bananas drill

or drill a free problem

1	`import math`
2
3	`class Solution:`
4	`def minEatingSpeed(self, piles: list[int], h: int) -> int:`
5	`left, right = 1, max(piles)`
6	`res = right`
7
8	`while left <= right:`
9	`k = (left + right) // 2`
10	`hours = 0`
11	`for p in piles:`
12	`hours += math.ceil(p / k)`
13
14	`if hours <= h:`
15	`res = min(res, k)`
16	`right = k - 1`
17	`else:`
18	`left = k + 1`
19
20	`return res`