Log inSign up
mediumleetcodeNot Started

Koko Eating Bananas

Koko loves to eat bananas. Given an integer array piles where piles[i] is the number of bananas in the ith pile and an integer h, return the minimum integer speed k such that Koko can eat all bananas within h hours.

Binary Search
Solve on leetcode
Lesson

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.\n\nKoko 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.\n\nKoko likes to eat slowly but still wants to finish eating all the bananas before the guards return.\n\nReturn the minimum integer k such that she can eat all the bananas within h hours.

Example 1 · Example 1: Standard Case:

Input: piles = [3, 6, 7, 11], h = 8
Output: 4
Explanation: At speed 4: ceil(3/4)=1, ceil(6/4)=2, ceil(7/4)=2, ceil(11/4)=3 -> 1+2+2+3 = 8 hours <= 8.

Example 2 · Example 2: Generous Hours:

Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Explanation: Since h equals piles.length, she must eat at max speed 30 to finish each pile in 1 hour.

Example 3 · Example 3: Large Hours Allowance:

Input: piles = [30, 11, 23, 4, 20], h = 6
Output: 23
Explanation: At speed 23: ceil(30/23)=2, ceil(11/23)=1, ceil(23/23)=1, ceil(4/23)=1, ceil(20/23)=1 -> 2+1+1+1+1 = 6 hours <= 6.

Constraints:

  • 1 <= piles.length <= 104
  • piles.length <= h <= 109
  • 1 <= piles[i] <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the classic 'Binary Search on Answer' paradigm.
  • Implement integer ceiling division (p + k - 1) / k correctly.
  • Handle 64-bit integer hour accumulation to prevent overflow.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find minimum integer value that satisfies a global threshold (h hours).
  • Feasibility function is strictly monotonic with respect to candidate value.
  • Constraints allow O(n log(max)) runtime.

Algorithmic Decision Tree:

  • low = 1, high = max(piles).
  • While low <= high: mid = low + (high - low) / 2.
  • Compute hours = sum((pile + mid - 1) / mid).
  • If hours <= h: ans = mid, high = mid - 1.
  • Else: low = mid + 1.
  • Return ans.

Connected Patterns:

Capacity To Ship Packages Within D DaysMinimum Number of Days to Make m BouquetsSplit Array Largest Sum

1. Linear Search Over Speeds

Intuition

Iterate speed k starting from 1 upwards. For each k, sum ceil(pile / k). Return the first k where total hours <= h.

When to apply: Basic baseline.

Algorithm

  1. Step 1: Loop speed k from 1 to max(piles).
  2. Step 2: Calculate total hours for speed k.
  3. Step 3: If total hours <= h, return k.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int minEatingSpeed(vector<int>& piles, int h) {
10 int maxVal = 0;
11 for (int p : piles) maxVal = max(maxVal, p);
12
13 for (int k = 1; k <= maxVal; ++k) {
14 long long totalHours = 0;
15 for (int p : piles) {
16 totalHours += (p + k - 1) / k;
17 }
18 if (totalHours <= h) return k;
19 }
20 return maxVal;
21 }
22};
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(n * max(piles)) — Can test up to 109 speeds, each taking O(n) time, resulting in TLE.
  • Space complexity: O(1) — O(1) auxiliary space.

2. Lower Bounded Linear Search

Intuition

Koko must eat at least ceil(sum(piles) / h) bananas per hour mathematically. Starting k from this lower bound skips unfeasible speeds.

When to apply: Heuristic optimization for small max values.

Algorithm

  1. Step 1: Compute totalSum = sum(piles).
  2. Step 2: Start k = ceil(totalSum / h).
  3. Step 3: Test speeds sequentially until totalHours <= h.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int minEatingSpeed(vector<int>& piles, int h) {
10 long long sum = 0;
11 int maxVal = 0;
12 for (int p : piles) {
13 sum += p;
14 maxVal = max(maxVal, p);
15 }
16 int startK = max(1LL, (sum + h - 1) / h);
17 for (int k = startK; k <= maxVal; ++k) {
18 long long totalHours = 0;
19 for (int p : piles) {
20 totalHours += (p + k - 1) / k;
21 }
22 if (totalHours <= h) return k;
23 }
24 return maxVal;
25 }
26};
27
28int main() {
29 // Sample driver execution
30 cout << "Execution completed successfully." << endl;
31 return 0;
32}
33

Time & Space Complexity

  • Time complexity: O(n * (max(piles) - sum/h)) — Still linear in max(piles) in worst case.
  • Space complexity: O(1) — O(1) extra space.

3. Binary Search on Answer

Intuition

Set low = 1, high = max(piles). In each step compute mid. Calculate total hours = sum((p + mid - 1) / mid). If total hours <= h, save ans = mid and try smaller speed with high = mid - 1; else low = mid + 1.

When to apply: Standard optimal solution.

Algorithm

  1. Step 1: low = 1, high = max(piles), ans = high.
  2. Step 2: While low <= high:
  3. - mid = low + (high - low) / 2.
  4. - totalHours = sum((pile + mid - 1) / mid).
  5. - If totalHours <= h: ans = mid, high = mid - 1.
  6. - Else low = mid + 1.
  7. Step 3: Return ans.

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

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Range [1, 11]
Visual state
Values and pointers at this exact step
pointers
S
27 hrs
10 hrs
8 hrs
6 hrs
4 hrs
0
↑ low
1
↑ low
2
3
↑ mid
4
↑ high
Check / comparison
Hours needed at speed 6: 6 hours <= h (8) -> Valid candidate.
Decision / next transition
Record ans = 6, set high = 5.
Why this step matters

Range [1, 11]. mid=6. Total hours: ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 <= 8. Valid speed! ans=6. Search left: high = mid - 1 = 5.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int minEatingSpeed(vector<int>& piles, int h) {
10 int low = 1, high = 0;
11 for (int p : piles) high = max(high, p);
12
13 int ans = high;
14 while (low <= high) {
15 int mid = low + (high - low) / 2;
16 long long totalHours = 0;
17 for (int p : piles) {
18 totalHours += (p + mid - 1) / mid;
19 }
20 if (totalHours <= h) {
21 ans = mid;
22 high = mid - 1;
23 } else {
24 low = mid + 1;
25 }
26 }
27 return ans;
28 }
29};
30
31int main() {
32 // Sample driver execution
33 cout << "Execution completed successfully." << endl;
34 return 0;
35}
36

Time & Space Complexity

  • Time complexity: O(n * log(max(piles))) — Binary search takes log2(max(piles)) iterations (at most 30 steps), each checking all n piles.
  • Space complexity: O(1) — Requires O(1) auxiliary variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Speed ScanO(n * max(piles))O(1)Test speeds 1, 2, 3... sequentially.Iterates through all possible speed values.
2.Bounded Linear ScanO(n * max(piles))O(1)Start linear scan from ceil(sum/h).Sequential candidate checking.
3.Binary Search on AnswerOptimalO(n * log(max(piles)))O(1)Binary search on monotonic speed space [1, max(piles)].None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • h == piles.length -> Koko must eat at speed max(piles) because she can only eat from 1 pile per hour.
  • piles with very large values (piles[i] = 109) -> accumulation of hours can exceed 32-bit int, use 64-bit integer for total hours.
  • piles has only 1 pile.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Define the lower bound (low = 1) and upper bound (high = max(piles)) clearly.
  2. Write a helper function canFinish(k, h) to keep code modular and readable.
  3. Show how integer ceiling division avoids floating point errors.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must totalHours be stored in a 64-bit integer (long long / long)?

Back to DSA Sheet