Logo

Kode$word

LeetCode 875: Koko Eating Bananas – Find the Minimum Eating Speed Using Binary Search
LeetCode 875: Koko Eating Bananas – Find the Minimum Eating Speed Using Binary Search

LeetCode 875: Koko Eating Bananas – Find the Minimum Eating Speed Using Binary Search

Step-by-Step Explanation of the Koko Eating Bananas Problem with Intuition, Dry Run, and Java Implementation

20 views
0
0
Binary SearchBinary Search on AnswerArraysLeetCodeMediumJava
Github icon

Try the Problem

You can practice the problem here:

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


Problem Description

Koko loves eating bananas 🍌.

You are given n piles of bananas, where the i-th pile contains piles[i] bananas.

The guards have left and will return after h hours. Koko wants to finish eating all the bananas before the guards come back.

Koko can choose her banana-eating speed k bananas per hour.

However, there are some important rules:

  1. Every hour, Koko chooses one pile of bananas.
  2. She eats k bananas from that pile.
  3. If the pile contains fewer than k bananas, she eats all of them and stops for that hour.
  4. She cannot move to another pile in the same hour.

Your task is to determine the minimum integer value of k such that Koko can finish all the bananas within h hours.


Example Walkthrough

Example 1

Input

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

Output

4

Explanation:

If Koko eats 4 bananas per hour, the time taken for each pile is:

3 bananas → 1 hour
6 bananas → 2 hours
7 bananas → 2 hours
11 bananas → 3 hours

Total time required:

1 + 2 + 2 + 3 = 8 hours

Since Koko finishes all bananas within 8 hours, the minimum speed is 4 bananas per hour.

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

Important observations:

  1. A pile may contain up to one billion bananas.
  2. The number of hours can also be extremely large.
  3. A naive solution may become computationally expensive.


Intuition Behind the Problem

The key observation in this problem is the relationship between eating speed and required hours.

If Koko eats slowly, she needs more hours.

If she eats faster, she needs fewer hours.

This creates a monotonic relationship:

Eating Speed ↑ → Hours Required ↓

Because of this property, we can apply Binary Search on the answer.

Instead of testing every possible eating speed, we can efficiently search the correct speed using binary search.


Approach 1: Brute Force

Idea

Try every possible eating speed:

k = 1 → max(piles)

For each speed:

  1. Calculate the total hours required.
  2. If the hours are less than or equal to h, return that speed.

Drawback

The maximum pile size can be:

10^9

Trying all speeds up to 10^9 would take too long.

Time Complexity

O(max(pile) × n)

This approach is not feasible for large inputs.


Approach 2: Binary Search on Answer (Optimal Solution)

Since the answer lies between 1 and the maximum pile size, we can apply binary search.

Search Space

Minimum possible speed:

1 banana/hour

Maximum possible speed:

max(piles)

Binary Search Strategy

  1. Choose a middle value mid as the candidate eating speed.
  2. Calculate how many hours Koko needs at this speed.
  3. If the hours are less than or equal to h, try a smaller speed.
  4. If the hours are greater than h, increase the speed.

This continues until we find the minimum valid speed.


Java Implementation

class Solution {

// Function to calculate total hours needed
// if Koko eats bananas at a given speed
public int hourCalculate(int[] piles, int speed){

int hours = 0;

// Traverse through each pile
for(int i = 0; i < piles.length; i++){

// Calculate hours needed for this pile
// Using ceiling division
hours += Math.ceil((double)piles[i] / speed);
}

return hours;
}


public int minEatingSpeed(int[] piles, int h) {

// Minimum possible eating speed
int low = 1;

// Maximum possible speed
int high = Integer.MIN_VALUE;

// Find the maximum pile
for(int pile : piles){
high = Math.max(high, pile);
}

int answer = high;

// Binary Search
while(low <= high){

int mid = low + (high - low) / 2;

// Calculate required hours at speed mid
int requiredHours = hourCalculate(piles, mid);

if(requiredHours <= h){

// mid is a valid answer
answer = mid;

// Try smaller speed
high = mid - 1;
}
else{

// Speed too slow
low = mid + 1;
}
}

return answer;
}
}

Time Complexity

Binary Search runs in:

O(log(max(pile)))

Each iteration calculates hours in:

O(n)

Overall complexity:

O(n log(max(pile)))

Space Complexity

O(1)

No extra memory is required.


Key Takeaway

This problem is a classic example of Binary Search on Answer.

Whenever a problem asks:

“Find the minimum or maximum value such that a condition is satisfied”

You should consider applying Binary Search on the answer space.


Conclusion

Instead of testing every possible eating speed, we used Binary Search to efficiently find the minimum speed that allows Koko to finish the bananas within the given number of hours.

This approach dramatically improves performance and is a common technique used in many coding interview problems involving optimization and search space reduction.

Related Articles

LeetCode 1482: Minimum Number of Days to Make m Bouquets – Binary Search on the Earliest Day

LeetCode 1482: Minimum Number of Days to Make m Bouquets – Binary Search on the Earliest Day

A Complete Guide to Solving the Bouquet Problem Using Binary Search on Answer with Intuition, Dry Run, and Java Implementation

Read Article
LeetCode 1283 — Find the Smallest Divisor Given a Threshold | Binary Search on Answer Explained

LeetCode 1283 — Find the Smallest Divisor Given a Threshold | Binary Search on Answer Explained

Another clean example of the "Binary Search on Answer" pattern — intuition, greedy check, commented Java code, dry run, and complexity analysis.

Read Article
LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

A Complete Guide to Solving “Find Unique Binary String” Using Hashing, Brute Force Thinking, and Cantor’s Diagonalization

Read Article
LeetCode 1011 — Capacity To Ship Packages Within D Days | Binary Search on Answer Explained

LeetCode 1011 — Capacity To Ship Packages Within D Days | Binary Search on Answer Explained

Master the "Binary Search on Answer" pattern with a complete walkthrough — intuition, dry run, commented Java code, and complexity analysis.

Read Article

Ai Assistant Kas