Koko Eating Bananas

Interview Problem Interview Medium Binary Search on Answer Array Binary Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.minEatingSpeed(piles, h). At an integer speed k, each pile takes ceil(pile/k) hours. Return the smallest speed that finishes all piles within h hours.

Starter code

class Solution:
    def minEatingSpeed(self, piles, h):
        pass

Test cases

sample-eight

{
  "args": [
    [
      3,
      6,
      7,
      11
    ],
    8
  ]
}

Expected: 4

Wizard outline

Step 1: Initialize Solution.minEatingSpeed
Replace the empty starter with the first real state owned by Solution.minEatingSpeed. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the One Pile Per Hour case
Complete the readable core algorithm for one representative Interview case. Binary-search the first feasible speed using total ceiling-division hours as a monotone predicate.
Step 3: Harden the Sample Eight boundary
Repair the reviewed boundary and pass the complete submission contract. If a speed is feasible, every larger speed is also feasible, so feasible speeds form a suffix. The lower-bound search preserves the first feasible speed and converges to its minimum.

Footguns and prerequisites

Ordinary floor division undercounts partially consumed piles; use (pile+speed-1)//speed.
arrays strings two pointers sliding window

Reviewed references

LeetCode 875 — Koko Eating Bananas

Practice prerequisites

Minimize a Feasible Value(opens in a new tab)
Minimize a Feasible Value isolates left is the first unresolved candidate and right is always a feasible candidate, so the smallest feasible value remains inside [left, right]. That focused state discipline is required when implementing koko eating bananas as a complete Interview Problem.

Recommended approach and implementation

Binary-search speeds from 1 through the largest pile and keep a speed when the sum of ceiling divisions fits h.

Why it works: If a speed is feasible, every larger speed is also feasible, so feasible speeds form a suffix. The lower-bound search preserves the first feasible speed and converges to its minimum.

class Solution:
    def minEatingSpeed(self, piles, h):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        left, right = 1, max(piles)
        while left < right:
            speed = (left + right) // 2
            hours = sum((pile + speed - 1) // speed for pile in piles)
            if hours <= h:
                right = speed
            else:
                left = speed + 1
        return left

Similar exercises

Ship Packages Within D Days(opens in a new tab)