Skip to content

Volume ITechnology

4.11.3 — Koko Eating Bananas ​

LeetCode 875 · Medium

The problem ​

There are n piles of bananas, given in a list called piles. Koko eats at a speed of k bananas per hour. Each hour, she picks one pile and eats up to k bananas from it. If that pile has fewer than k left, she finishes it and rests for the rest of the hour. She never moves on to a second pile within the same hour.

She has h hours. Return the smallest whole-number speed k that lets her finish every pile within h hours.

piles = [3, 6, 7, 11],      h = 8   →  4
piles = [30, 11, 23, 4, 20], h = 5   →  30

For example, a pile of 10 bananas at speed 3 takes 4 hours: 3, then 3, then 3, then the last 1.

There are up to 10,000 piles. Each pile can hold up to 1,000,000,000 bananas, and h is at least the number of piles, so an answer always exists.

What the problem is really asking ​

There is no sorted list here, and nothing obvious to search. But turn the question around. Instead of "what is the best speed?", ask a simpler yes/no question:

At speed k, can she finish in time?

That is easy to answer. Work out the hours for each pile, add them up, and compare with h. A pile of size p at speed k takes p \div k hours, rounded up, because a part-finished pile still costs a whole hour:

\text{hours for a pile} = \left\lceil \frac{p}{k} \right\rceil

The symbols \lceil \ \rceil mean ceiling, which means "round up to the next whole number". \lceil 10 / 3 \rceil = \lceil 3.33 \rceil = 4.

Now look at how the yes/no answer changes as the speed goes up.

speed k:    1    2    3    4    5    6   ...
in time?   no   no   no   yes  yes  yes  ...
                          ↑
                     the answer

Once a speed is fast enough, every faster speed is also fast enough. The answers go "no, no, no", then "yes, yes, yes", and never switch back. That is exactly the monotonic yes/no shape from the end of 4.11.1. So we can binary search the speed itself.

This move is called binary search on the answer. Check three things before you use it.

  1. The answer is a number inside a range you know.
  2. "Does this value work?" is easy to check.
  3. If a value works, every bigger value works too (or every smaller one, depending on the problem).

The brute force, and where it wastes work ​

Try every speed from 1 upward, and stop at the first that works.

python
def minEatingSpeed(piles, h):
    k = 1
    while sum((p + k - 1) // k for p in piles) > h:   # too slow
        k += 1
    return k

If the answer is a billion, this checks a billion speeds, and each check walks all 10,000 piles. That is 10^{13} steps.

The waste in one sentence: it tests speeds one at a time, when each "too slow" answer also proves that every slower speed is too slow.

The range ​

What is the slowest speed worth trying? 1 banana per hour.

What is the fastest speed worth trying? The size of the biggest pile. At that speed, every pile takes exactly 1 hour. Going any faster cannot help, because she can only eat from one pile per hour anyway.

So the answer lies between 1 and max(piles).

The solution ​

python
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def hours_needed(k: int) -> int:                       # (1)
            return sum((p + k - 1) // k for p in piles)

        low, high = 1, max(piles)                              # (2)

        while low < high:                                      # (3)
            mid = low + (high - low) // 2
            if hours_needed(mid) <= h:                         # (4)
                high = mid
            else:                                              # (5)
                low = mid + 1

        return low                                             # (6)
ts
function minEatingSpeed(piles: number[], h: number): number {
  const hoursNeeded = (k: number) =>                           // (1)
    piles.reduce((sum, p) => sum + Math.ceil(p / k), 0);

  let low = 1, high = Math.max(...piles);                      // (2)

  while (low < high) {                                         // (3)
    const mid = low + Math.floor((high - low) / 2);
    if (hoursNeeded(mid) <= h) high = mid;                     // (4)
    else low = mid + 1;                                        // (5)
  }

  return low;                                                  // (6)
}

Line by line ​

(1) How many hours does speed k need? Add up the rounded-up hours for every pile. (p + k - 1) // k is how you round a division up using only whole numbers. This is how it works.

// divides and rounds down. To round up instead, add just enough to push any leftover past the next whole number. k - 1 is exactly enough.

  • If p divides exactly by k, adding k - 1 is not enough to reach the next multiple, so the answer does not change. For p = 6, k = 3: (6 + 2) // 3 = 8 // 3 = 2. ✓
  • If there is any leftover, adding k - 1 pushes it over. For p = 7, k = 3: (7 + 2) // 3 = 9 // 3 = 3. ✓

Why not math.ceil(p / k)? Because p / k makes a decimal first. Very large numbers cannot always be stored exactly as decimals, so the rounding can come out wrong. Whole-number arithmetic has no such limit. In TypeScript, Math.ceil(p / k) is fine here, because the numbers in this problem are small enough to be exact.

(2) The range of speeds, from 1 to the biggest pile.

(3) Shape B from 4.11.1: find a boundary. We are not looking for one exact value. We are looking for the point where "too slow" turns into "fast enough". So the loop runs while low < high, and it ends when the range has shrunk to a single speed.

(4) Fast enough at mid. Then mid might be the answer, or something slower might also work. So we keep mid in the range with high = mid. Using mid - 1 here would throw away a speed that could be the answer.

(5) Too slow at mid. Then mid and every slower speed are useless. Move low past it.

(6) low and high have met on the slowest speed that works.

Trace ​

Take piles = [3, 6, 7, 11] and h = 8. The range is 1 to 11.

SteplowhighmidHours at midWithin 8?Action
111161 + 1 + 2 + 2 = 6yeshigh = 6
21631 + 2 + 3 + 4 = 10nolow = 4
34651 + 2 + 2 + 3 = 8yeshigh = 5
44541 + 2 + 2 + 3 = 8yeshigh = 4
end44return 4

Check the hours in step 2 by hand. At speed 3: the pile of 3 takes 1 hour, the pile of 6 takes 2, the pile of 7 takes \lceil 7/3 \rceil = 3, and the pile of 11 takes \lceil 11/3 \rceil = 4. That is 10 hours, more than 8, so speed 3 is too slow.

Complexity, derived ​

Let n be the number of piles and M the biggest pile.

Time. The binary search runs over the range 1 to M, so it takes about \log_2 M steps. For M = one billion, that is about 30 steps. Each step calls hours_needed, which walks all n piles. So the total is O(n \log M).

Notice that the \log is over the size of the values, not the number of piles. That is typical of binary search on the answer, and it is why the method stays cheap even when the range of answers is enormous.

Space. A few numbers, so O(1).

Edge cases ​

  • h equals the number of piles. She must finish each pile in one hour, so the answer is the biggest pile.
  • h is huge. The answer can be 1.
  • One pile. The answer is that pile's size divided by h, rounded up.

Variations you will meet ​

Each of these is the same ten lines with a different "does this value work?" check.

  • Capacity to Ship Packages Within D Days. Find the smallest ship capacity that delivers all packages, in order, within D days. The check walks the packages, starting a new day whenever the next one will not fit. The range runs from the heaviest package to the total weight.
  • Split Array Largest Sum. The same problem as shipping, worded as cutting a list into parts.
  • Find the Smallest Divisor Given a Threshold. The check is this page's rounded-up sum, almost exactly.
  • Minimum Number of Days to Make m Bouquets. The check walks the flowers, counting runs of neighbours that have bloomed.

How to recognise the family: the problem says minimise the maximum, maximise the minimum, or find the smallest value such that…. That wording almost always means binary search on the answer.

What the interviewer will push on ​

"Why can you binary search when nothing is sorted?" Because the yes/no answers over the speeds are monotonic. State the three conditions.

"What is your range, and why?" 1 to the biggest pile. Faster than the biggest pile gains nothing, because she eats from only one pile per hour.

"Why high = mid and not mid - 1?" A speed that works might be the answer, so it stays in the range.

"Why whole-number ceiling division?" Decimals can lose accuracy on large numbers. (p + k - 1) // k is always exact.

"What is the complexity?" O(n \log M). Point out that the \log is over the values.

One thing to volunteer: name the technique and state the monotonic property in one sentence. "If speed k finishes in time, every faster speed does too, so I can binary search the speed."

Next: 4.11.4 Find Minimum in Rotated Sorted Array. Back to a list, but one whose sorted order has been broken in exactly one place.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet