Koko Eating Bananas

Learning goal: Translate the eating process into a decision problem that can be searched efficiently.

Core idea For a fixed speed k, each pile is independent. A pile of size p takes ceil(p / k) hours, so the total time is the sum of those rounded-up quotients. We need the smallest speed whose total time is at most h.

Algorithm plan

• Choose a candidate speed k.
• Compute hours = sum(ceil(pile / k)).
• If hours <= h, the speed works; try smaller speeds.
• Otherwise, the speed is too slow; try larger speeds.

Micro-example For piles = [3,6,7,11] and k = 4, the hours are 1 + 2 + 2 + 3 = 8. Since 8 <= h, speed 4 is feasible.

Pitfalls

• A pile that is not evenly divisible still needs a full final hour.
• The answer is a speed, not an index or an existing pile value.
• The goal is the minimum feasible speed, not merely any feasible speed.

Recap

• Test a speed with a total-hours calculation.
• Feasibility determines whether to move lower or higher.
• Minimize the speed while staying within the hour limit.

Learning goal: Recognize why binary search applies even though the piles themselves are not sorted.

Core idea As speed increases, the hours required for every pile can only stay the same or decrease. Therefore, feasibility has a monotonic shape: slow speeds fail, then all sufficiently fast speeds succeed. Binary search does not need sorted input values here; it needs a monotonic yes/no predicate over the candidate answers.

Algorithm plan

• Lower bound: left = 1, because speed zero cannot make progress.
• Upper bound: right = max(piles), because this speed finishes the largest pile in one hour and is always sufficient when h >= piles.length.
• Let mid be the candidate speed.
• Keep the feasible half when mid works; otherwise keep the faster half.

Micro-example For [3,6,7,11], speeds 1, 2, and 3 fail for h = 8, while speed 4 and every faster speed succeed. The transition is between 3 and 4.

Pitfalls

• Do not search values in the array; the answer may be 4 even though 4 is not a pile size.
• The correct search space is every integer speed in [1, max pile].
• Use a lower-bound style loop so the first feasible speed is retained.

Recap

• Feasibility is monotonic in speed.
• Search the answer space, not the input array.
• Return the leftmost feasible speed.

Learning goal: Build the complete binary-search algorithm and its feasibility calculation.

Core idea The candidate speed is the value being searched. For each mid, calculate a pile's hours with integer arithmetic: ceil(pile / mid) equals (pile + mid - 1) // mid. If the total is within h, mid might be the answer, so move right left to search smaller speeds.

Algorithm plan

1. Set left = 1 and right = max(piles).
2. While left < right, compute mid = (left + right) // 2.
3. Sum (pile + mid - 1) // mid for every pile.
4. If the sum is at most h, set right = mid; otherwise set left = mid + 1.
5. Return left.

while left < right:
    mid = (left + right) // 2
    hours = sum((p + mid - 1) // mid for p in piles)
    if hours <= h:
        right = mid
    else:
        left = mid + 1
return left

Micro-example With bounds [1,11], mid = 6 needs 6 hours, so the answer is at most 6. The next candidate is tested in [1,5].

Pitfalls

• Do not use ordinary division without rounding up.
• Use mid + 1 after failure; the failed speed cannot be the answer.
• Use a wide integer type for the hour sum in languages with fixed-width integers.

Recap

• A feasibility check costs O(n).
• Each binary-search step discards half the speed range.
• The final lower bound is the smallest feasible speed.

Learning goal: Avoid the common boundary and interpretation errors in answer-space binary search.

Core idea The input array does not define the sorted search domain. The possible answer is any integer speed from 1 through max(piles), including values that do not appear in piles. Correct bounds and ceiling division are the details that make the monotonic predicate reliable.

Algorithm plan

• Initialize the lower bound to 1, not 0.
• Initialize the upper bound to the largest pile.
• Count each pile with ceiling division.
• On feasibility, keep mid by assigning right = mid.
• On failure, exclude mid with left = mid + 1.

Micro-example For [3,6,7,11], searching only the pile values would examine [3,6,7,11] and could miss the true answer 4. The answer space [1,11] contains every possible speed.

Pitfalls

• pile // k undercounts whenever a remainder exists.
• If h == piles.length, the answer is max(piles).
• A single pile works as a valid input, including when h is larger than one.
• Do not return the first feasible mid; continue searching left.

Recap

• Search speeds, not pile entries.
• Round every pile's hours upward.
• Preserve feasible mid values while narrowing to the minimum.

Learning goal: Explain the efficiency of the final solution and recognize the reusable pattern.

Core idea Each feasibility check scans all n piles once, so it costs O(n). Binary search performs O(log max(piles)) checks because the speed interval is repeatedly halved. The implementation stores only a few variables beyond the input, giving constant auxiliary space.

Algorithm plan

• Define a monotonic predicate: canFinish(k).
• Search the integer answer range [1, max(piles)].
• Keep a feasible midpoint as a possible answer.
• Remove failed speeds and return the collapsed lower bound.

Micro-example For the walkthrough, the range size is 11 and only three candidate checks are needed: speeds 6, 3, and 4. Each check scans the four piles.

Pitfalls

• State the monotonic predicate before writing the loop.
• Distinguish O(n log max(piles)) from O(n log n); the logarithm is over the answer range.
• The result is a speed, not the number of hours or the largest pile.

Recap

• Time: O(n log max(piles)).
• Auxiliary space: O(1).
• The reusable pattern is binary search on a monotonic answer predicate.