65. Koko Eating Bananas

🔗 LeetCode Problem: 875. Koko Eating Bananas
📊 Difficulty: Medium
🏷️ Topics: Array, Binary Search

Problem Statement

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints: - 1 <= piles.length <= 10^4 - piles.length <= h <= 10^9 - 1 <= piles[i] <= 10^9

🎨 Visual Understanding

The Problem Visualized

Example 1: piles = [3, 6, 7, 11], h = 8

If k = 4 (eating speed):
  Pile 1 (3 bananas):  1 hour (eats all 3)
  Pile 2 (6 bananas):  2 hours (4 + 2)
  Pile 3 (7 bananas):  2 hours (4 + 3)
  Pile 4 (11 bananas): 3 hours (4 + 4 + 3)

  Total: 1 + 2 + 2 + 3 = 8 hours ✓

If k = 3:
  Pile 1: 1 hour
  Pile 2: 2 hours
  Pile 3: 3 hours (3 + 3 + 1)
  Pile 4: 4 hours (3 + 3 + 3 + 2)

  Total: 1 + 2 + 3 + 4 = 10 hours ✗ (exceeds 8)

Minimum k = 4

Example 2: piles = [30, 11, 23, 4, 20], h = 5

Number of piles = 5
Hours available = 5
Must use exactly 1 hour per pile!

Eating speed must be at least max(piles) = 30
If k = 30, each pile takes 1 hour = 5 hours ✓

Answer: k = 30

Visual representation of eating process:

piles = [3, 6, 7, 11], k = 4

Hour 1: Pile 1 → eat 3 (done) ✓
Hour 2: Pile 2 → eat 4 (2 left)
Hour 3: Pile 2 → eat 2 (done) ✓
Hour 4: Pile 3 → eat 4 (3 left)
Hour 5: Pile 3 → eat 3 (done) ✓
Hour 6: Pile 4 → eat 4 (7 left)
Hour 7: Pile 4 → eat 4 (3 left)
Hour 8: Pile 4 → eat 3 (done) ✓

All piles finished in 8 hours!

🚨 CRITICAL INSIGHT - Binary Search on Answer Space!

The Key Pattern!

This is "Binary Search on Answer" pattern!

What are we searching?
  NOT searching in the array
  Searching for OPTIMAL VALUE of k (eating speed)

Search Space:
  Minimum k: 1 banana/hour
  Maximum k: max(piles) bananas/hour

  Range: [1, max(piles)]

Key Property (Monotonic):
  If k works (can finish in h hours):
    → Any k' > k also works (faster)

  If k doesn't work:
    → Any k' < k also doesn't work (slower)

  Pattern: [NO NO NO NO | YES YES YES YES]
           [too slow    | fast enough    ]
                        ↑
                  Find this boundary!

We want: MINIMUM k that works
       = Find FIRST "YES"
       = Binary search for leftmost valid!

How to Check if k Works

For a given speed k, can Koko finish in h hours?

Calculate hours needed for each pile:
  pile = 7, k = 4
  hours = ceil(7 / 4) = ceil(1.75) = 2 hours

  pile = 11, k = 4
  hours = ceil(11 / 4) = ceil(2.75) = 3 hours

Total hours = sum of ceil(pile / k) for all piles

If total <= h: k works! ✓
If total > h: k too slow ✗

Mathematical formula:
  hours_for_pile = (pile + k - 1) / k  (integer division)
  OR
  hours_for_pile = ceil(pile / k)

Why Binary Search Works

Example: piles = [3, 6, 7, 11], h = 8

Search space: k ∈ [1, 11]

Test different speeds:
  k = 1:  Takes 3+6+7+11 = 27 hours ✗
  k = 2:  Takes 2+3+4+6 = 15 hours ✗
  k = 3:  Takes 1+2+3+4 = 10 hours ✗
  k = 4:  Takes 1+2+2+3 = 8 hours ✓
  k = 5:  Takes 1+2+2+3 = 8 hours ✓
  k = 6:  Takes 1+1+2+2 = 6 hours ✓
  ...
  k = 11: Takes 1+1+1+1 = 4 hours ✓

Pattern: [✗ ✗ ✗ | ✓ ✓ ✓ ✓ ...]
         [1 2 3 | 4 5 6 7 ...]
                ↑
         Find this first YES!

Binary search finds the boundary efficiently!

🎯 Approach 1: Linear Search (Brute Force)

The Most Natural Thinking 💭

Core Logic:

Try each speed from 1 to max(piles):
  Check if speed k allows finishing in h hours
  Return first k that works

Implementation

public int minEatingSpeed(int[] piles, int h) {
    // Find max pile
    int maxPile = 0;
    for (int pile : piles) {
        maxPile = Math.max(maxPile, pile);
    }

    // Try each speed from 1 to maxPile
    for (int k = 1; k <= maxPile; k++) {
        if (canFinish(piles, h, k)) {
            return k;
        }
    }

    return maxPile;
}

private boolean canFinish(int[] piles, int h, int k) {
    long hours = 0;
    for (int pile : piles) {
        hours += (pile + k - 1) / k;  // Ceiling division
    }
    return hours <= h;
}

⏰ Time: O(n × max(piles)) - Try each speed, check each pile
💾 Space: O(1) - Only variables

❌ Problem: Too slow! max(piles) can be 10^9!

🎯 Approach 2: Binary Search on Answer (Optimal) ⭐

Better Approach 💡

🧠 The Core Insight

Search space: [1, max(piles)]
Property: Monotonic (if k works, k+1 works)
Goal: Find MINIMUM k that works

Perfect for binary search!

The Strategy:

Binary Search on Speed k:

1. left = 1, right = max(piles)
2. While left < right:
   a. mid = left + (right - left) / 2
   b. If canFinish(piles, h, mid):
      mid works, try smaller
      right = mid
   c. Else:
      mid too slow, need larger
      left = mid + 1
3. Return left

Implementation

public int minEatingSpeed(int[] piles, int h) {
    // Find the maximum pile size (upper bound for k)
    int left = 1;
    int right = 0;
    for (int pile : piles) {
        right = Math.max(right, pile);
    }

    // Binary search for minimum valid k
    while (left < right) {
        int mid = left + (right - left) / 2;

        if (canFinish(piles, h, mid)) {
            // mid works, try to find smaller
            right = mid;
        } else {
            // mid too slow, need faster
            left = mid + 1;
        }
    }

    return left;
}

// Check if eating speed k allows finishing in h hours
private boolean canFinish(int[] piles, int h, int k) {
    long hoursNeeded = 0;

    for (int pile : piles) {
        // Calculate hours for this pile (ceiling division)
        hoursNeeded += (pile + k - 1) / k;

        // Early termination if already exceeds h
        if (hoursNeeded > h) {
            return false;
        }
    }

    return hoursNeeded <= h;
}

⏰ Time: O(n × log(max(piles))) - Binary search × checking all piles
💾 Space: O(1) - Only variables

🔍 Dry Run

Example 1: piles = [3, 6, 7, 11], h = 8

Goal: Find minimum k

Find max: right = 11
Initial: left = 1, right = 11

Iteration 1:
  mid = 1 + (11 - 1) / 2 = 6

  Can finish with k = 6?
    Pile 3: (3+6-1)/6 = 8/6 = 1 hour
    Pile 6: (6+6-1)/6 = 11/6 = 1 hour
    Pile 7: (7+6-1)/6 = 12/6 = 2 hours
    Pile 11: (11+6-1)/6 = 16/6 = 2 hours
    Total: 1+1+2+2 = 6 hours <= 8 ✓

  Works! Try smaller
  right = 6
  Range: [1, 6]

Iteration 2:
  mid = 1 + (6 - 1) / 2 = 3

  Can finish with k = 3?
    Pile 3: (3+3-1)/3 = 5/3 = 1 hour
    Pile 6: (6+3-1)/3 = 8/3 = 2 hours
    Pile 7: (7+3-1)/3 = 9/3 = 3 hours
    Pile 11: (11+3-1)/3 = 13/3 = 4 hours
    Total: 1+2+3+4 = 10 hours > 8 ✗

  Too slow! Need faster
  left = 4
  Range: [4, 6]

Iteration 3:
  mid = 4 + (6 - 4) / 2 = 5

  Can finish with k = 5?
    Pile 3: (3+5-1)/5 = 7/5 = 1 hour
    Pile 6: (6+5-1)/5 = 10/5 = 2 hours
    Pile 7: (7+5-1)/5 = 11/5 = 2 hours
    Pile 11: (11+5-1)/5 = 15/5 = 3 hours
    Total: 1+2+2+3 = 8 hours <= 8 ✓

  Works! Try smaller
  right = 5
  Range: [4, 5]

Iteration 4:
  mid = 4 + (5 - 4) / 2 = 4

  Can finish with k = 4?
    Pile 3: (3+4-1)/4 = 6/4 = 1 hour
    Pile 6: (6+4-1)/4 = 9/4 = 2 hours
    Pile 7: (7+4-1)/4 = 10/4 = 2 hours
    Pile 11: (11+4-1)/4 = 14/4 = 3 hours
    Total: 1+2+2+3 = 8 hours <= 8 ✓

  Works! Try smaller
  right = 4
  Range: [4, 4]

Loop ends (left == right)
return 4 ✓

Example 2: piles = [30, 11, 23, 4, 20], h = 5

Max: 30
Initial: left = 1, right = 30

Iteration 1:
  mid = 15
  Can finish with k = 15?
    30/15 = 2 hours
    11/15 = 1 hour
    23/15 = 2 hours
    4/15 = 1 hour
    20/15 = 2 hours
    Total: 8 hours > 5 ✗

  Too slow
  left = 16

Iteration 2:
  mid = 23
  Can finish with k = 23?
    30/23 = 2 hours
    11/23 = 1 hour
    23/23 = 1 hour
    4/23 = 1 hour
    20/23 = 1 hour
    Total: 6 hours > 5 ✗

  Too slow
  left = 24

Iteration 3:
  mid = 27
  Can finish with k = 27?
    30/27 = 2 hours
    Others all = 1 hour each
    Total: 6 hours > 5 ✗

  Too slow
  left = 28

Continue converging...

Final: left = 30
return 30 ✓

(With 5 piles and 5 hours, need max speed)

🎯 Why This Works - Deep Dive

The Ceiling Division Formula:
═══════════════════════════════════════════════════════════════

hours = ceil(pile / k)

In integer arithmetic:
  ceil(a / b) = (a + b - 1) / b

Why?
  Example: pile = 7, k = 4
  7 / 4 = 1.75 → ceil = 2
  (7 + 4 - 1) / 4 = 10 / 4 = 2 ✓

This avoids floating point operations!

The Monotonic Property:
═══════════════════════════════════════════════════════════════

If speed k allows finishing in time:
  → Any k' > k also works (faster)

If speed k is too slow:
  → Any k' < k is also too slow

This creates sorted pattern:
  [NO NO NO | YES YES YES]
          ↑
    Find boundary

The "Find First Valid" Pattern:
═══════════════════════════════════════════════════════════════

Loop: while (left < right)
  Converge to minimum valid

When valid: right = mid
  mid works, but try smaller
  Keep mid in range

When invalid: left = mid + 1
  mid doesn't work, exclude it

Return: left (minimum valid speed)

Search Space Optimization:
═══════════════════════════════════════════════════════════════

Why right = max(piles)?
  If k >= max(piles):
    Each pile takes at most 1 hour
    Total hours = number of piles

  Larger k doesn't help!
  (Can't go faster than 1 hour per pile)

So max useful k = max(piles)

Time Complexity:
═══════════════════════════════════════════════════════════════

Binary search: O(log(max(piles)))
Each check: O(n) to sum all piles
Total: O(n × log(max(piles)))

Compare with linear: O(n × max(piles))
Much better when max(piles) is large!

Integer Overflow Prevention

// CRITICAL: Use long for hours
private boolean canFinish(int[] piles, int h, int k) {
    long hoursNeeded = 0;  // Must be long!

    for (int pile : piles) {
        hoursNeeded += (pile + k - 1) / k;
    }

    return hoursNeeded <= h;
}

// Why long?
// piles can have up to 10^4 elements
// Each pile can need multiple hours
// Total could exceed int range (2^31)

⚠️ Common Mistakes to Avoid

Mistake 1: Wrong ceiling formula

// ❌ WRONG - Floating point issues
int hours = (int) Math.ceil((double) pile / k);

// ✓ CORRECT - Integer arithmetic
int hours = (pile + k - 1) / k;

Mistake 2: Wrong loop condition

// ❌ WRONG - May not converge
while (left <= right) {
    if (canFinish(piles, h, mid)) {
        right = mid;  // Infinite loop risk!
    }
}

// ✓ CORRECT
while (left < right) {
    if (canFinish(piles, h, mid)) {
        right = mid;
    }
}

Mistake 3: Not using long

// ❌ WRONG - Integer overflow
int hoursNeeded = 0;
hoursNeeded += (pile + k - 1) / k;

// ✓ CORRECT
long hoursNeeded = 0;
hoursNeeded += (pile + k - 1) / k;

Mistake 4: Wrong initial bounds

// ❌ WRONG
int left = 0;  // Should be 1
int right = sum(piles);  // Too large!

// ✓ CORRECT
int left = 1;  // Minimum speed
int right = max(piles);  // Maximum useful speed

Mistake 5: Wrong return

// ❌ WRONG
return right;  // Could be wrong

// ✓ CORRECT
return left;  // Converged to minimum

🎯 Pattern Recognition

Problem Type: Binary Search on Answer Space
Core Pattern: Find Minimum Value Satisfying Constraint

When to Apply:
✓ Need to find OPTIMAL value (not in array)
✓ Can CHECK if value works
✓ Monotonic property exists
✓ Range of possible values known
✓ Checking is faster than trying all

Recognition Keywords:
- "Minimum" or "Maximum"
- "At least" or "At most"
- "Can do X in Y time/space"
- Optimization problem
- Constraint satisfaction

Similar Problems:
- Capacity to Ship Packages (LC 1011)
- Split Array Largest Sum (LC 410)
- Minimum Speed to Arrive on Time (LC 1870)
- Magnetic Force Between Balls (LC 1552)

Key Pattern Elements:
┌────────────────────────────────────────────┐
│ Binary Search on Answer:                   │
│ 1. Define search space [min, max]         │
│ 2. Write check function (can achieve?)    │
│ 3. Binary search for boundary              │
│ 4. Return optimal value                    │
│                                            │
│ Monotonic property:                        │
│   If X works → X+1 works (for minimum)    │
│   If X fails → X-1 fails (for minimum)    │
└────────────────────────────────────────────┘

NOT searching in array, searching for value!

🧠 Interview Strategy

Step 1: "Find minimum k → Binary search on answer"
Step 2: "Search space: [1, max(piles)]"
Step 3: "Check function: can finish in h hours?"
Step 4: "Monotonic: if k works, k+1 works"
Step 5: "Find first valid k"

Key Points to Mention:
- Binary search on ANSWER (not array)
- Search space: [1, max(piles)]
- Check: sum of ceil(pile/k) <= h
- Ceiling: (pile + k - 1) / k
- Monotonic property
- Find minimum valid k
- Loop: while (left < right)
- When valid: right = mid
- When invalid: left = mid + 1
- Use long for overflow
- Time: O(n log(max(piles)))

Why This Approach?
"This is a binary search on answer space problem. I'm not
searching for k in the array - I'm searching for the optimal
value of k in the range [1, max(piles)]. The key insight is
that if speed k allows Koko to finish in time, any faster
speed also works. This monotonic property lets me use binary
search. For each candidate speed, I check if it's valid by
calculating total hours needed using ceiling division. I find
the minimum valid speed by converging left and right pointers."

Ceiling Division:
"To calculate hours for a pile, I use (pile + k - 1) / k
which is the integer arithmetic equivalent of ceil(pile/k).
This avoids floating point operations and is more efficient."

Why max(piles)?
"The maximum useful eating speed is max(piles) because going
faster doesn't help - Koko can only eat from one pile per
hour, so the minimum time is already one hour per pile when
k >= max(piles)."

📝 Quick Revision Notes

🎯 Core Concept:

Binary Search on Answer: NOT searching array, searching for optimal k in [1, max(piles)]. Check if k works: sum of ceil(pile/k) <= h. Monotonic: if k works, k+1 works. Find minimum valid k. Ceiling: (pile + k - 1) / k. Use long!

⚡ Quick Implementation:

import java.util.Arrays;

class Test {
  public int minEatingSpeed(int[] a, int h) {
    // Search space is from (1, max(a)). Answer can be anything in between.
    // Worse case is 1 and best case is max(a) depending upon hours.
    // If you get more hours, you can eat 1-1-1-1...  so that k would be small
    // and need to be as per question.
    // If you get less hours, no options, you need to eat more and more per day
    // in which case k would be more which koko does not like.
    // We need to find a minimal k in which koko would eat all piles in <= h hours.
    int left = 1;
    int right = Arrays.stream(a).max().getAsInt();

    // Same template as earlier (peak/minimum etc) - check below points 1, 2 and 3.
    while (left < right) { // point 1
      int mid = left + (right - left) / 2;

      if(canFinish(a, h, mid)) {
        // lets check better which is minimum than mid (left side)
        right = mid; // point 2
      } else {
        left = mid + 1;
      }
    }

    return left; // point 3
  }

  private boolean canFinish(int[] a, int h, int k) {
    int hoursTaken = 0;

    for(int i = 0; i < a.length; i++) {
      int count = (a[i] % k == 0) ? (a[i] / k) : (a[i] / k) + 1;
      hoursTaken = hoursTaken + count;
    }

    return hoursTaken <= h;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.minEatingSpeed(new int[] {3,6,7,11}, 8) == 4);
    System.out.println(t.minEatingSpeed(new int[] {30,11,23,4,20}, 5) == 30);
    System.out.println(t.minEatingSpeed(new int[] {30,11,23,4,20}, 6) == 23);
    System.out.println(t.minEatingSpeed(new int[] {30}, 10) == 3);
    System.out.println(t.minEatingSpeed(new int[] {30, 11, 23, 4, 20}, 5) == 30);
    System.out.println(t.minEatingSpeed(new int[] {3, 6, 7, 11}, 100) == 1);
    System.out.println(t.minEatingSpeed(new int[] {5, 5, 5, 5}, 8) == 3);
    System.out.println(t.minEatingSpeed(new int[] {1000000000}, 2) == 500000000);

  }
}

🔑 Key Insights:

Pattern: Binary Search on Answer Space
Search Space: [1, max(piles)]
Check Function: Can finish in h hours?
Ceiling Formula: (pile + k - 1) / k
Monotonic: k works → k+1 works
Find: Minimum valid k
Loop: while (left < right)
Valid: right = mid (try smaller)
Invalid: left = mid + 1 (need larger)
Overflow: Use long hours
Time: O(n × log(max)), Space: O(1)

🎪 Memory Aid:

"Search for speed, not in array! Ceiling divide, check if valid!"
Think: "Answer space, monotonic, find minimum!"

💡 The Key Insight:

NOT searching IN array
Searching FOR optimal value

If k works:
  Try smaller: right = mid

If k doesn't work:
  Need larger: left = mid + 1

Converge to minimum valid!

⚠️ Critical Details:

1. Search space: [1, max(piles)]
2. Ceiling: (pile + k - 1) / k ← NOT Math.ceil!
3. Sum: long hours = 0 ← Overflow prevention!
4. Check: hours <= h
5. Valid: right = mid ← Keep mid!
6. Invalid: left = mid + 1
7. Return: left ← Minimum valid

🔥 The Ceiling Trick:

Why (pile + k - 1) / k works:

pile = 7, k = 4
7 / 4 = 1 (integer division)
But we need 2 hours!

(7 + 4 - 1) / 4 = 10 / 4 = 2 ✓

General formula:
ceil(a/b) = (a + b - 1) / b

Avoids floating point!

💡 Monotonic Property:

piles = [3, 6, 7, 11], h = 8

k=1: 27 hours ✗
k=2: 15 hours ✗
k=3: 10 hours ✗
k=4:  8 hours ✓
k=5:  8 hours ✓
k=6:  6 hours ✓
...

Pattern: [✗ ✗ ✗ | ✓ ✓ ✓ ...]
                ↑
         Find this!

🧪 Edge Cases

Case 1: One pile

Input: piles = [30], h = 10
Output: 3
(Need at least 30/10 = 3 bananas/hour)

Case 2: h equals number of piles

Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30
(Need max speed to finish 1 pile per hour)

Case 3: Plenty of time

Input: piles = [3, 6, 7, 11], h = 100
Output: 1
(Can go slowest speed)

Case 4: All piles equal

Input: piles = [5, 5, 5, 5], h = 8
Output: 3
(ceil(5/3) = 2 hours each, total 8)

Case 5: Large numbers

Input: piles = [1000000000], h = 2
Output: 500000000
(Need half the pile per hour)

All handled correctly with long! ✓

Capacity to Ship Packages (LC 1011) - Same pattern
Split Array Largest Sum (LC 410) - Binary search on answer
Minimum Speed to Arrive on Time (LC 1870) - Similar concept

Happy practicing! 🎯

Note: This is THE classic "binary search on answer space" problem! Master this pattern - it appears in many optimization problems!

65. Koko Eating Bananas

Problem Statement

🎨 Visual Understanding

The Problem Visualized

🚨 CRITICAL INSIGHT - Binary Search on Answer Space!

How to Check if k Works

Why Binary Search Works

🎯 Approach 1: Linear Search (Brute Force)

The Most Natural Thinking 💭

Implementation

🎯 Approach 2: Binary Search on Answer (Optimal) ⭐

Better Approach 💡

Implementation

🔍 Dry Run

🎯 Why This Works - Deep Dive

Integer Overflow Prevention

⚠️ Common Mistakes to Avoid

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

🧪 Edge Cases

Related Patterns