LeetCode 875: Koko Eating Bananas

https://leetcode.com/problems/koko-eating-bananas/description/ 

Piles:    📦  📦  📦  📦        → 4 piles
Hours:    ⏰  ⏰  ⏰  ⏰  ⏰  ⏰   → 6 hours
✅ piles.length <= h — We have at least one hour per pile, so Koko can eat all piles, even at slow speed.

❌ Why we can’t have h < piles.length

Piles:    📦  📦  📦  📦        → 4 piles
Hours:    ⏰  ⏰  ⏰             → Only 3 hours
In this case, even if Koko eats one full pile per hour, she cannot finish all piles in time.
That’s why h must be at least the number of piles.

✅ Why is high = (int) 1e9; valid?
The problem constraint says:
1 <= piles[i] <= 10^9

This means the maximum number of bananas in any pile can be up to 1 billion.

So the maximum possible speed Koko might need is:
k = 1e9 bananas/hour

This represents the worst case — if she only had 1 hour, and one pile had 1e9 bananas, she'd need a speed of 1e9.
So by setting:
high = (int) 1e9;
You're defining the upper bound of the binary search correctly.
🔄 Tradeoff Summary

Step
Option 1: 1e9
Option 2: max from array
Initial setup time
O(1)
O(n)
Binary search steps
O(log(1e9)) ≈ 30
O(log(maxPile)) → usually < 30
Total time
Slightly more overall
Slightly optimized

💡 Approach: Binary Search on k
We search for the minimum value of k such that the total time to eat all bananas ≤ h.
Steps:
Search Space:
low = 1 (minimum speed)
high = max(piles) (maximum speed needed if she finishes one pile per hour)
Better TC: high = (int) 1e9;
Binary Search:
For a middle value k, calculate total hours required.
If total hours <= h, it’s a valid k, so try smaller.
If hours > h, increase k.

Binary Search Simulation:
Search space: low = 1, high = max(piles) = 11
Try different k values and apply checker():

Try k
Time per pile
Total Time
Valid?
Adjust
6
 ceil(3/6)+ceil(6/6)+
 ceil(9/6)+ceil(11/6) =   1+1+2+2
6
✅ Yes
Try smaller k → high = 5
3
 1+2+3+4 = 10
❌ No
Too slow → low = 4
4
 1+2+3+3 = 9
❌ No
Too slow → low = 5
5
 1+2+2+3 = 8
✅ Yes
Save k=5, try smaller → high = 4

public class KoKoBanana {
    public static void main(String[] args) {
        // TC: O(1), SC: O(1) – variable and array initialization
        int[] piles = {3, 6, 9, 11};
        int h = 8;

        // TC: O(log(max(piles)) * n), SC: O(1)
        System.out.println(minEatingSpeed(piles, h));
    }

    private static int minEatingSpeed(int[] piles, int h) {
        // TC: O(1), SC: O(1) – initial bounds
        int low = 1, high = (int) 1e9;
        int aspeed = (int) 1e9;

        // Binary search loop
        // TC: O(log(max_speed)) ~ O(log(1e9)) = O(30)
        while (low <= high) {
            int mid = low + (high - low) / 2; // O(1)
            // this is used, to keep mid in range of int

            // Each checker call: O(n) where n = piles.length
            if (checker(piles, mid, h)) {
                aspeed = mid; // O(1)
                high = mid - 1; // O(1)
            } else {
                low = mid + 1; // O(1)
            }
        }
        return aspeed; // O(1)
    }

    private static boolean checker(int[] piles, int speed, int h) {
        int time = 0;
        for (int nob : piles) {
            // TC: O(1) per pile, total O(n)
            time += Math.ceil(nob / (1.0 * speed));
        }
        return time <= h; // O(1)
    }
}

Case
Time Complexity
Space Complexity
Explanation
Best Case
O(n)
O(1)
If the first mid value satisfies the time ≤ h condition.
Average Case
O(n * log(max(pile)))
O(1)
Binary search with checker() over log(max(pile)) iterations.
Worst Case
O(n * log(max(pile)))
O(1)
All log(max_speed) iterations required to converge.

🔁 Example Best Case Scenario:

Let's say:
piles = {4, 2, 3, 6}
h = 4

If mid = 6 (i.e., speed = 6) is guessed on the first try, and it's valid, then binary search stops immediately. But checker() still needs to do:
ceil(4/6) + ceil(2/6) + ceil(3/6) + ceil(6/6)
= 1 + 1 + 1 + 1 = 4 hours

✅ All 4 elements processed → O(n) as array is not sorted.