BS-12. Koko Eating Bananas

Koko loves to eat bananas, but she has a strict deadline of $H$ hours to finish $n$ piles of bananas. The challenge is to find the minimum integer eating speed $K$ (bananas per hour) that allows Koko to consume all the bananas within the given time limit. This classic problem serves as a primary template for mastering the Binary Search on Answers pattern.

1. Why Do We Need This? (Problem Statement & Constraints)

• The Setup: You are given an array of integers representing $n$ piles of bananas (e.g., [3, 6, 7, 11]), and an integer $H$ representing the maximum allowable hours (e.g., $H = 8$).
• The Rule: Koko can choose to eat at a speed of $K$ bananas per hour. However, she must obey two strict eating constraints:
  1. She can only eat from one pile at a time.
  2. If a pile has fewer than $K$ bananas, she finishes the pile in that hour and cannot move on to the next pile until the next hour begins (i.e., time cannot be carried over or fractionally shared across piles).
• The Objective: Find the minimum integer $K$ such that the total hours taken across all piles is $\le H$.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: The Speed Limit Search

Imagine you are driving a car on a toll road with a strict arrival deadline. If you drive too slow (small $K$), you will take too long and miss your deadline. If you drive too fast (large $K$), you will make it easily, but you are burning excessive energy. Your goal is to find the absolute minimum speed required to arrive on time.

• Pile Division & Ceiling Rule: Because Koko cannot consume a fraction of an hour on a partial pile (e.g., eating 3 bananas at a speed of 2 bananas/hour takes $1.5$ hours, which rounds up to 2 hours), we must always take the ceiling value of the division:

3. Naive vs. Better Approach

The Naive Linear Search Approach

• Start with the minimum possible eating speed $K = 1$.
• Calculate the total hours required to finish all piles at speed $K = 1$.
• If the total hours exceed $H$, increment $K$ by 1 ($K = 2$) and repeat.
• Stop at the first $K$ where the total hours $\le H$.

• Limitation: The linear search approach checks every integer sequentially up to the maximum possible answer, leading to an inefficient time complexity of $O(\text{Max}(\text{array}) \times n)$, which will trigger a Time Limit Exceeded (TLE) error in competitive programming.

4. Step-by-Step Evolution: Discovering Binary Search on Answers

When examining the outcome of different speeds $K$, a distinct boolean monotonic pattern emerges:

• The Monotonic Pattern: As $K$ increases, the total hours required strictly decrease. Once a speed $K$ is fast enough to meet the deadline, all speeds greater than $K$ are also valid.
• This creates a clear partition: [Not Possible, Not Possible, ..., Possible, Possible, Possible].
• Because the search space is sorted and bounded, we can replace linear traversal with Binary Search on Answers.

5. Determining the Search Range (Low and High)

To execute binary search, we must define our search boundaries:

• Low: The minimum possible bananas per hour Koko can eat is 1.
• High: The maximum sensible speed is eating the largest single pile in one hour. Even if Koko eats at a rate equal to the maximum element in the array, she clears any pile in 1 hour. Therefore, High = Max(piles).

6. Complete Flow Walkthrough (Example: piles = [3, 6, 7, 11], $H = 8$)

1. Initialize Range: Low = 1, High = 11.
2. Iteration 1:
   • Mid = (1 + 11) / 2 = 6.
   • Compute hours for $K = 6$: $\lceil 3/6 \rceil + \lceil 6/6 \rceil + \lceil 7/6 \rceil + \lceil 11/6 \rceil = 1 + 1 + 2 + 2 = 6$ hours.
   • Is $6 \le 8$? Yes (Possible).
   • Save potential answer as 6 and search the left half for a smaller valid speed: High = Mid - 1 ($5$).
3. Iteration 2:
   • Low = 1, High = 5.
   • Mid = (1 + 5) / 2 = 3.
   • Compute hours for $K = 3$: $\lceil 3/3 \rceil + \lceil 6/3 \rceil + \lceil 7/3 \rceil + \lceil 11/3 \rceil = 1 + 2 + 3 + 4 = 10$ hours.
   • Is $10 \le 8$? No (Not Possible).
   • Eliminate the invalid left half: Low = Mid + 1 ($4$).
4. Iteration 3:
   • Low = 4, High = 5.
   • Mid = (4 + 5) / 2 = 4.
   • Compute hours for $K = 4$: $\lceil 3/4 \rceil + \lceil 6/4 \rceil + \rceil 7/4 \rceil + \rceil 11/4 \rceil = 1 + 2 + 2 + 3 = 8$ hours.
   • Is $8 \le 8$? Yes (Possible).
   • Save potential answer as 4 and search left: High = Mid - 1 ($3$).
5. Termination: Loop terminates because Low (4) > High (3). The answer 4 is successfully returned.

7. Real-World Practical Pitfalls & Edge Cases

• Integer Division Trap:
  • When calculating $\lceil \text{Pile}[i] / K \rceil$ in programming languages like C++, Java, or Python, doing integer division (pile / K) truncates decimals instead of ceiling them.
  • Solution: Cast operands to floating-point numbers before division, or use integer arithmetic trick for ceiling: (pile + K - 1) / K.
• Large Array Values:
  • If pile sizes are extremely large, ensure your variables (low, high, mid, total hours) use appropriate data types (long long in C++) to prevent integer overflow.

8. Reference Implementation (Pseudo-Code / C++ Style)

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Function to calculate total hours required at a given eating speed 'hourly'
    long long calculateTotalHours(vector<int>& piles, int hourly) {
        long long totalHours = 0;
        for (int i = 0; i < piles.size(); i++) {
            // Equivalent to ceil(piles[i] / hourly) without precision loss
            totalHours += (piles[i] + hourly - 1) / hourly;
        }
        return totalHours;
    }

public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int low = 1;
        int high = *max_element(piles.begin(), piles.end());
        int ans = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            long long totalHours = calculateTotalHours(piles, mid);

            if (totalHours <= h) {
                ans = mid;          // Possible answer found, try looking for a smaller speed
                high = mid - 1;     // Eliminate right half
            } else {
                low = mid + 1;      // Too slow, increase speed by eliminating left half
            }
        }
        return ans;
    }
};

9. Complexity Analysis

• Time Complexity:
  • Finding the maximum element in the piles array takes $O(n)$.
  • The binary search runs in $O(\log(\text{Max}(\text{piles})))$ iterations.
  • Inside the binary search loop, calculateTotalHours scans all $n$ piles, taking $O(n)$ time.
  • Total Time Complexity: $O(n \times \log(\text{Max}(\text{piles})))$, which is exceptionally fast and easily passes all runtime constraints.
• Space Complexity: $O(1)$ auxiliary space, as we only use a few pointers (low, high, mid, ans) for binary search.

Summary and Key Takeaways

• Problem Class Identification: Whenever a problem asks for the "minimum integer" or "maximum integer" within a monotonic range of feasibility (not possible $\to$ possible), Binary Search on Answers is the optimal strategy.
• Range Definition: For Koko Eating Bananas, the search space bounds are strictly defined from 1 (minimum possible speed) to Max(piles) (upper bound speed).
• The Ceiling Function: Always account for partial hours correctly by applying ceiling division ((pile + K - 1) / K) when calculating consumption rates across discrete piles.
• Optimal Efficiency: Replacing linear search with binary search reduces time complexity from $O(\text{Max}(\text{piles}) \times n)$ down to $O(n \times \log(\text{Max}(\text{piles})))$.
• Pointer Convergence: Notice how low and high naturally isolate the optimal boundary condition upon loop termination, offering a robust template for similar search space problems.