Koko Eating Bananas - Practice Coding Problems

Koko Eating Bananas - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: At speed k=4: pile 3 takes ceil(3/4)=1 hour, pile 6 takes ceil(6/4)=2 hours, pile 7 takes ceil(7/4)=2 hours, pile 11 takes ceil(11/4)=3 hours. Total: 1+2+2+3=8 hours, which equals h=8.

Example 2 — Tight Constraint

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

› Output: 30

💡 Note: With 5 piles and 5 hours, Koko must finish at least one pile per hour. The largest pile is 30, so minimum speed is 30 bananas/hour.

Example 3 — Plenty of Time

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

› Output: 23

💡 Note: At speed k=23: takes ceil(30/23)+ceil(11/23)+ceil(23/23)+ceil(4/23)+ceil(20/23) = 2+1+1+1+1 = 6 hours exactly.

Constraints

1 ≤ piles.length ≤ 10⁴
piles.length ≤ h ≤ 10⁹
1 ≤ piles[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Banana piles and time limit h

Process

Find minimum eating speed k

Output

Minimum k to finish within h hours

Key Takeaway

🎯 Key Insight: Binary search on eating speed leverages the monotonic property - if speed k works, all speeds > k also work

Asked in

F Facebook 25 a Amazon 18 G Google 15 M Microsoft 12

The key insight is that this is a binary search on answer space problem. If Koko can finish eating at speed k, she can also finish at any speed > k. We want the minimum k that works. Best approach is binary search on eating speed from 1 to max(piles). Time: O(n × log(max(piles))), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer Space	O(n × log(max(piles)))	O(1)	Binary search on the eating speed k from 1 to max(piles) to find minimum valid speed
Brute Force Linear Search	O(n × max(piles))	O(1)	Try every eating speed from 1 to max(piles) until finding the minimum that works

Binary Search on Answer Space — Algorithm Steps

Set search range: left = 1, right = max(piles)
For mid speed, calculate if Koko can finish within h hours
If yes, try smaller speeds (right = mid). If no, need bigger speeds (left = mid + 1)
Return left when search completes

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Range

Search space [1, max(piles)]

Test Middle

Check if mid speed works

Narrow Range

Eliminate half based on result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canFinish(int* piles, int pilesSize, int h, int k) {
    int hours = 0;
    for (int i = 0; i < pilesSize; i++) {
        hours += (piles[i] + k - 1) / k; // Ceiling division
    }
    return hours <= h;
}

int solution(int* piles, int pilesSize, int h) {
    int left = 1, right = 0;
    for (int i = 0; i < pilesSize; i++) {
        if (piles[i] > right) {
            right = piles[i];
        }
    }
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(piles, pilesSize, h, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int piles[1000];
    int pilesSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || strcmp(token, "0") == 0) {
            piles[pilesSize++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int h;
    scanf("%d", &h);
    
    int result = solution(piles, pilesSize, h);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(max(piles)))

Binary search takes log(max(piles)) iterations, each iteration processes n piles

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for binary search variables

✓ Linear Space

157.0K Views

Medium Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer Space — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler