How do you solve Koko Eating Bananas on LeetCode?

Koko Eating Bananas (LeetCode #875) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log m) time complexity and O(1) space complexity. Key insight: Binary search allows us to efficiently narrow down the possible eating speeds.

What is the brute force solution for Koko Eating Bananas?

The brute force approach for Koko Eating Bananas is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves trying every possible eating speed k from 1 to the maximum number of bananas in any pile. For each k, we simulate the eating process to see if Koko can finish all the bananas in h hours. The optimal Optimal Solution approach improves this to O(n log m).

What algorithm or data structure is used to solve Koko Eating Bananas?

Koko Eating Bananas uses the following concepts: Array, Binary Search. The recommended patterns to study are: Binary Search, Greedy.

What are the interview tips for Koko Eating Bananas?

Explain your thought process clearly as you work through the problem. Practice writing the binary search pattern, as it's common in many problems. Always consider edge cases, such as very small or very large values in the input.

What are common mistakes when solving Koko Eating Bananas?

Not considering the ceiling division when calculating hours. Forgetting to check the boundaries of the binary search properly.

#875

Koko Eating Bananas

Medium

ArrayBinary SearchBinary SearchGreedy

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log m)
Space	O(1)	O(1)

💡

Intuition

Time O(n log m)Space O(1)

The optimal approach uses binary search to efficiently find the minimum eating speed k. We search for k in the range from 1 to the maximum pile size, checking if Koko can finish all bananas within h hours for each mid value of k.

⚙️

Algorithm

5 steps

1Step 1: Set low to 1 and high to the maximum number of bananas in any pile.
2Step 2: While low is less than or equal to high, calculate mid as the average of low and high.
3Step 3: Calculate the total hours needed to eat all bananas at speed mid.
4Step 4: If the total hours exceed h, increase low to mid + 1 (need a faster speed). Otherwise, set high to mid - 1 (check for a slower speed).
5Step 5: Return low as the minimum speed k.

solution.py10 lines

1def minEatingSpeed(piles, h):
2    low, high = 1, max(piles)
3    while low <= high:
4        mid = (low + high) // 2
5        hours = sum((pile + mid - 1) // mid for pile in piles)
6        if hours > h:
7            low = mid + 1
8        else:
9            high = mid - 1
10    return low

ℹ

Complexity note: The time complexity is O(n log m) where n is the number of piles and m is the maximum number of bananas in any pile. The log m comes from the binary search over possible speeds.

1Binary search allows us to efficiently narrow down the possible eating speeds.
2Understanding how to calculate hours based on eating speed is crucial.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.