Koko Eating Bananas

🎯

Koko Eating Bananas

mediumBINARY_SEARCHAmazonGoogleFacebook

Koko loves eating bananas but wants to finish them all before the guards come back. She needs to figure out the minimum speed to eat all bananas within a limited time.

💡 This problem is a classic example of binary search on the answer space rather than on the input array. Beginners often struggle because they try to apply binary search directly on the array elements instead of searching over possible speeds. Understanding how to define and check feasibility is key.

📋

Problem Statement

Koko has n piles of bananas, where piles[i] is the number of bananas in the ith pile. Guards will come back in h hours. Koko can decide her eating speed k (bananas per hour). Each hour, she chooses a pile and eats k bananas from it. If the pile has less than k bananas, she eats all of them and stops eating for that hour. Return the minimum integer k such that Koko can eat all bananas within h hours.

1 ≤ piles.length ≤ 10^51 ≤ piles[i] ≤ 10^9piles.length ≤ h ≤ 10^9

💡

Example

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

Output4

At speed 4, Koko can finish piles in 8 hours: 3/4=1h, 6/4=2h, 7/4=2h, 11/4=3h total 8h.

• Single pile with bananas equal to h → minimum speed is 1
• All piles have 1 banana and h equals number of piles → minimum speed is 1
• Very large piles with h equal to number of piles → minimum speed equals max pile size
• h is much larger than number of piles → minimum speed can be 1

⚠️

Common Mistakes

Using binary search on the piles array instead of the speed range

Incorrect answer or failure to converge

✅ Binary search must be on the speed range [1, max pile size], not on piles themselves

Not using ceiling division when calculating hours

Underestimates hours needed, leading to wrong feasibility results

✅ Use ceiling division: hours += (pile + speed - 1) // speed or math.ceil(pile / speed)

Not handling the case when h equals number of piles

May return speed less than max pile size, which is invalid

✅ Ensure feasibility function and binary search handle this edge case correctly

Not stopping early in feasibility check

Unnecessary computation leading to slower runtime

✅ Add early stopping if hours exceed h during feasibility check

Using floating point division without ceiling

Incorrect hours calculation due to truncation

✅ Always use integer ceiling division to count hours correctly

🧠

Brute Force (Linear Search on Speed)

💡 This approach tries every possible speed from 1 up to the maximum pile size. It is straightforward and helps understand the problem constraints and feasibility check, but it is inefficient for large inputs.

Intuition

Try all speeds starting from 1 upwards, and for each speed, check if Koko can finish all bananas within h hours. The first speed that satisfies this is the answer.

Algorithm

1. Find the maximum pile size as the upper bound for speed.
2. For speed from 1 to max pile size:
3. Calculate total hours needed to eat all piles at this speed.
4. If total hours ≤ h, return this speed as the answer.

💡 The main challenge is realizing that speed can be any integer between 1 and max pile size, and checking feasibility is straightforward but costly.

</>

Code

from math import ceil

def minEatingSpeed(piles, h):
    max_speed = max(piles)
    for speed in range(1, max_speed + 1):
        hours = 0
        for pile in piles:
            hours += ceil(pile / speed)
        if hours <= h:
            return speed

# Driver code
if __name__ == '__main__':
    piles = [3,6,7,11]
    h = 8
    print(minEatingSpeed(piles, h))  # Output: 4

Line Notes

max_speed = max(piles)Find the maximum pile size to set the upper bound for speed.

for speed in range(1, max_speed + 1)Try every possible speed from 1 to max_speed.

hours += ceil(pile / speed)Calculate hours needed to finish current pile at this speed.

if hours <= hCheck if total hours is within allowed time.

import java.util.*;

public class KokoEatingBananas {
    public static int minEatingSpeed(int[] piles, int h) {
        int maxSpeed = 0;
        for (int pile : piles) maxSpeed = Math.max(maxSpeed, pile);
        for (int speed = 1; speed <= maxSpeed; speed++) {
            int hours = 0;
            for (int pile : piles) {
                hours += (pile + speed - 1) / speed;
            }
            if (hours <= h) return speed;
        }
        return maxSpeed;
    }

    public static void main(String[] args) {
        int[] piles = {3,6,7,11};
        int h = 8;
        System.out.println(minEatingSpeed(piles, h)); // Output: 4
    }
}

Line Notes

int maxSpeed = 0;Initialize maxSpeed to find upper bound for speed.

for (int speed = 1; speed <= maxSpeed; speed++)Try all speeds from 1 to maxSpeed.

hours += (pile + speed - 1) / speed;Calculate hours needed for current pile using integer division ceiling trick.

if (hours <= h) return speed;Return speed if total hours fit within h.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minEatingSpeed(vector<int>& piles, int h) {
    int maxSpeed = *max_element(piles.begin(), piles.end());
    for (int speed = 1; speed <= maxSpeed; speed++) {
        long long hours = 0;
        for (int pile : piles) {
            hours += (pile + speed - 1) / speed;
        }
        if (hours <= h) return speed;
    }
    return maxSpeed;
}

int main() {
    vector<int> piles = {3,6,7,11};
    int h = 8;
    cout << minEatingSpeed(piles, h) << endl; // Output: 4
    return 0;
}

Line Notes

int maxSpeed = *max_element(piles.begin(), piles.end());Find max pile size as upper bound for speed.

for (int speed = 1; speed <= maxSpeed; speed++)Try all speeds from 1 to maxSpeed.

hours += (pile + speed - 1) / speed;Calculate hours needed for each pile with ceiling division.

if (hours <= h) return speed;Return speed if total hours is within limit.

function minEatingSpeed(piles, h) {
    const maxSpeed = Math.max(...piles);
    for (let speed = 1; speed <= maxSpeed; speed++) {
        let hours = 0;
        for (const pile of piles) {
            hours += Math.ceil(pile / speed);
        }
        if (hours <= h) return speed;
    }
    return maxSpeed;
}

// Driver code
const piles = [3,6,7,11];
const h = 8;
console.log(minEatingSpeed(piles, h)); // Output: 4

Line Notes

const maxSpeed = Math.max(...piles);Find maximum pile size as upper bound for speed.

for (let speed = 1; speed <= maxSpeed; speed++)Try every speed from 1 to maxSpeed.

hours += Math.ceil(pile / speed);Calculate hours needed for current pile at this speed.

if (hours <= h) return speed;Return speed if total hours fit within h.

⏱

Complexity

TimeO(n * max(piles))

SpaceO(1)

For each speed from 1 to max pile size, we iterate over all piles to calculate hours. max(piles) can be up to 10^9, making this approach infeasible for large inputs.

💡 If n=10^5 and max pile size=10^9, this means up to 10^14 operations, which is impossible to run in reasonable time.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and feasibility check.

🧠

Binary Search on Answer Space

💡 This approach uses binary search on the range of possible speeds to efficiently find the minimum speed. It leverages the monotonicity of the feasibility function, which is a key insight for this problem.

Intuition

The minimum speed lies between 1 and max pile size. We use binary search to guess a speed and check if Koko can finish in h hours. If yes, try smaller speeds; if no, try larger speeds.

Algorithm

1. Set low = 1 and high = max pile size.
2. While low < high:
3. mid = (low + high) // 2
4. If Koko can finish all piles at speed mid within h hours, set high = mid.
5. Else, set low = mid + 1.
6. Return low as the minimum speed.

💡 The key is defining the feasibility function and using binary search to narrow down the minimum speed efficiently.

</>

Code

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += ceil(pile / speed)
    return hours <= h

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(piles, mid, h):
            high = mid
        else:
            low = mid + 1
    return low

# Driver code
if __name__ == '__main__':
    piles = [3,6,7,11]
    h = 8
    print(minEatingSpeed(piles, h))  # Output: 4

Line Notes

def can_finish(piles, speed, h):Defines feasibility function to check if speed is sufficient.

hours += ceil(pile / speed)Calculate hours needed for each pile at given speed.

while low < high:Binary search loop to narrow down minimum speed.

if can_finish(piles, mid, h):If feasible, try smaller speeds by moving high down.

import java.util.*;

public class KokoEatingBananas {
    private static boolean canFinish(int[] piles, int speed, int h) {
        int hours = 0;
        for (int pile : piles) {
            hours += (pile + speed - 1) / speed;
        }
        return hours <= h;
    }

    public static int minEatingSpeed(int[] piles, int h) {
        int low = 1, high = 0;
        for (int pile : piles) high = Math.max(high, pile);
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canFinish(piles, mid, h)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] piles = {3,6,7,11};
        int h = 8;
        System.out.println(minEatingSpeed(piles, h)); // Output: 4
    }
}

Line Notes

private static boolean canFinish(int[] piles, int speed, int h)Feasibility function to check if speed suffices.

hours += (pile + speed - 1) / speed;Calculate hours needed for each pile with ceiling division.

while (low < high)Binary search loop to find minimum speed.

if (canFinish(piles, mid, h))If feasible, try smaller speeds by adjusting high.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canFinish(const vector<int>& piles, int speed, int h) {
    long long hours = 0;
    for (int pile : piles) {
        hours += (pile + speed - 1) / speed;
    }
    return hours <= h;
}

int minEatingSpeed(vector<int>& piles, int h) {
    int low = 1, high = *max_element(piles.begin(), piles.end());
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canFinish(piles, mid, h)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int main() {
    vector<int> piles = {3,6,7,11};
    int h = 8;
    cout << minEatingSpeed(piles, h) << endl; // Output: 4
    return 0;
}

Line Notes

bool canFinish(const vector<int>& piles, int speed, int h)Feasibility function to check if speed suffices.

hours += (pile + speed - 1) / speed;Calculate hours needed for each pile with ceiling division.

while (low < high)Binary search loop to find minimum speed.

if (canFinish(piles, mid, h))If feasible, try smaller speeds by adjusting high.

function canFinish(piles, speed, h) {
    let hours = 0;
    for (const pile of piles) {
        hours += Math.ceil(pile / speed);
    }
    return hours <= h;
}

function minEatingSpeed(piles, h) {
    let low = 1, high = Math.max(...piles);
    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (canFinish(piles, mid, h)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// Driver code
const piles = [3,6,7,11];
const h = 8;
console.log(minEatingSpeed(piles, h)); // Output: 4

Line Notes

function canFinish(piles, speed, h)Feasibility function to check if speed suffices.

hours += Math.ceil(pile / speed);Calculate hours needed for each pile at given speed.

while (low < high)Binary search loop to find minimum speed.

if (canFinish(piles, mid, h))If feasible, try smaller speeds by adjusting high.

⏱

Complexity

TimeO(n log m)

SpaceO(1)

Binary search runs in log(max pile size) steps, and each step checks all piles (n). This is efficient for large inputs.

💡 If n=10^5 and max pile size=10^9, this means about 30 * 10^5 = 3 million operations, which is feasible.

Interview Verdict: Accepted

This is the optimal and accepted approach for this problem in interviews.

🧠

Binary Search with Early Stopping in Feasibility Check

💡 This approach optimizes the feasibility check by stopping early if the hours exceed h, saving unnecessary computation.

Intuition

While checking feasibility for a given speed, if the total hours already exceed h, we can stop checking further piles and return false immediately.

Algorithm

1. Set low = 1 and high = max pile size.
2. While low < high:
3. mid = (low + high) // 2
4. Check feasibility with early stopping:
5. Sum hours for piles, stop if sum > h.
6. If feasible, set high = mid; else low = mid + 1.
7. Return low.

💡 Early stopping reduces unnecessary work in feasibility checks, improving average runtime.

</>

Code

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += ceil(pile / speed)
        if hours > h:
            return False
    return True

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(piles, mid, h):
            high = mid
        else:
            low = mid + 1
    return low

# Driver code
if __name__ == '__main__':
    piles = [3,6,7,11]
    h = 8
    print(minEatingSpeed(piles, h))  # Output: 4

Line Notes

hours += ceil(pile / speed)Add hours needed for current pile.

if hours > h:Early stop if hours exceed allowed time.

while low < high:Binary search loop to find minimum speed.

if can_finish(piles, mid, h):Adjust high if feasible.

import java.util.*;

public class KokoEatingBananas {
    private static boolean canFinish(int[] piles, int speed, int h) {
        int hours = 0;
        for (int pile : piles) {
            hours += (pile + speed - 1) / speed;
            if (hours > h) return false;
        }
        return true;
    }

    public static int minEatingSpeed(int[] piles, int h) {
        int low = 1, high = 0;
        for (int pile : piles) high = Math.max(high, pile);
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canFinish(piles, mid, h)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] piles = {3,6,7,11};
        int h = 8;
        System.out.println(minEatingSpeed(piles, h)); // Output: 4
    }
}

Line Notes

hours += (pile + speed - 1) / speed;Add hours needed for current pile.

if (hours > h) return false;Early stop if hours exceed allowed time.

while (low < high)Binary search loop to find minimum speed.

if (canFinish(piles, mid, h))Adjust high if feasible.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canFinish(const vector<int>& piles, int speed, int h) {
    long long hours = 0;
    for (int pile : piles) {
        hours += (pile + speed - 1) / speed;
        if (hours > h) return false;
    }
    return true;
}

int minEatingSpeed(vector<int>& piles, int h) {
    int low = 1, high = *max_element(piles.begin(), piles.end());
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canFinish(piles, mid, h)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int main() {
    vector<int> piles = {3,6,7,11};
    int h = 8;
    cout << minEatingSpeed(piles, h) << endl; // Output: 4
    return 0;
}

Line Notes

hours += (pile + speed - 1) / speed;Add hours needed for current pile.

if (hours > h) return false;Early stop if hours exceed allowed time.

while (low < high)Binary search loop to find minimum speed.

if (canFinish(piles, mid, h))Adjust high if feasible.

function canFinish(piles, speed, h) {
    let hours = 0;
    for (const pile of piles) {
        hours += Math.ceil(pile / speed);
        if (hours > h) return false;
    }
    return true;
}

function minEatingSpeed(piles, h) {
    let low = 1, high = Math.max(...piles);
    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (canFinish(piles, mid, h)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// Driver code
const piles = [3,6,7,11];
const h = 8;
console.log(minEatingSpeed(piles, h)); // Output: 4

Line Notes

hours += Math.ceil(pile / speed);Add hours needed for current pile.

if (hours > h) return false;Early stop if hours exceed allowed time.

while (low < high)Binary search loop to find minimum speed.

if (canFinish(piles, mid, h))Adjust high if feasible.

⏱

Complexity

TimeO(n log m)

SpaceO(1)

Early stopping reduces average time spent in feasibility checks but worst-case remains the same as approach 2.

💡 This optimization helps especially when h is small and many speeds are infeasible, saving time by not checking all piles.

Interview Verdict: Accepted

This is a practical optimization that can improve runtime in interviews and real-world scenarios.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, you should implement the binary search on answer space with early stopping. Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Linear Search on Speed)	O(n * max(pile))	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Binary Search on Answer Space	O(n log max(pile))	O(1)	No	N/A	Optimal approach to implement
3. Binary Search with Early Stopping	O(n log max(pile)) (better average runtime)	O(1)	No	N/A	Optimal approach with practical optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, introduce binary search on the answer space as the optimal solution. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem constraints and inputs.Step 2: Describe the brute force approach and its limitations.Step 3: Introduce binary search on the answer space and explain feasibility function.Step 4: Code the binary search solution with early stopping optimization.Step 5: Test with sample and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to recognize binary search on answer space, define a correct feasibility function, and optimize your solution for large inputs.

Common Follow-ups

• What if h is less than number of piles? → Impossible, return max pile size or handle invalid input.
• Can you optimize the feasibility check? → Use early stopping to reduce runtime.

💡 These follow-ups test your understanding of constraints and your ability to optimize code beyond the basic solution.

🔍

Pattern Recognition

When to Use

1) You need to minimize or maximize a numeric answer. 2) The answer lies within a known numeric range. 3) You can check feasibility of a candidate answer efficiently. 4) The feasibility function is monotonic.

Signature Phrases

minimum integer kcan finish all bananas within h hoursfind the least speed

NOT This Pattern When

This is not a classic binary search on sorted arrays problem; the search is on the answer space, not input data.

Similar Problems

Capacity To Ship Packages Within D Days - similar binary search on minimum capacitySplit Array Largest Sum - binary search on maximum subarray sumMinimum Time to Complete Trips - binary search on minimum time

Practice

1. Consider the following Python function maxDistanceOptimized that finds the largest minimum distance to place m balls in sorted positions. Given position = [1, 2, 4, 8] and m = 3, what is the final returned value?

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Trace binary search boundaries

   Initial low=1, high=7 (8-1). Mid=4: can_place(4)? Positions: 1,2,4,8. Place first ball at 1, next at 8 (8-1=7≥4), count=2 < m=3 -> False.

2. Step 2: Adjust boundaries and find final result

   high=3, mid=2: can_place(2)? Place at 1, then 4 (4-1=3≥2), then 8 (8-4=4≥2), count=3 -> True. low=3, mid=3: can_place(3)? Place at 1, then 4 (3≥3), then 8 (4≥3), count=3 -> True. low=4, high=3 ends loop. Result=3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Final max minimum distance is 3 [OK]

Hint: Check feasibility at mid distances carefully [OK]

Common Mistakes:

• Off-by-one in binary search boundaries
• Miscounting balls placed in can_place

2. You are given a sorted array and a target value. You need to find the index where the target should be inserted to maintain the sorted order. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that inserts the target at the first position where the next element is larger

B. Linear scan from the start to find the first element greater than or equal to the target

C. Dynamic programming that builds solutions for subproblems of smaller arrays

D. Binary search that repeatedly halves the search space to find the correct insertion index

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so searching can be optimized by halving the search space instead of scanning linearly.

2. Step 2: Identify the algorithm that efficiently finds insertion index

   Binary search divides the array repeatedly, guaranteeing O(log n) time, which is optimal compared to linear or DP approaches.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search is the classic approach for sorted array search problems [OK]

Hint: Sorted array + insertion -> binary search [OK]

Common Mistakes:

• Assuming greedy insertion is always optimal
• Confusing DP with binary search
• Using linear scan despite sorted input

3. Identify the bug in the following modified code snippet for the Minimum Days to Make m Bouquets problem:

medium

A. The feasibility function does not reset flowers count correctly.

B. Binary search boundaries are incorrectly set from 0 instead of min bloom day.

C. The initial check for m * k > n is missing, causing unnecessary computation.

D. Early stopping in feasibility function is missing, causing slower runtime.

Solution

1. Step 1: Check initial conditions

   The code lacks the check if m * k > n, which means it's impossible to make required bouquets.

2. Step 2: Consequences of missing check

   Without this, the code runs unnecessary binary search and feasibility checks, possibly returning wrong answers or timing out.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding the initial impossible case check fixes the bug. [OK]

Hint: Always check if total flowers suffice before processing [OK]

Common Mistakes:

• Forgetting impossible case check
• Misresetting flowers count in feasibility

4. The following code attempts to find the insert position of a target in a sorted array using recursive binary search. Identify the line containing the subtle bug that can cause incorrect results or infinite recursion.

medium

A. Line 3: if left > right: return right

B. Line 4: mid = (left + right) // 2

C. Line 7: if nums[mid] == target: return mid

D. Line 9: return binary_search(mid + 1, right)

Solution

1. Step 1: Analyze base case return value

   When left > right, the correct insertion index is left, not right.

2. Step 2: Consequence of returning right

   Returning right can cause incorrect insertion index or infinite recursion if right < left.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct base case returns left to indicate insertion point [OK]

Hint: Base case must return left, not right [OK]

Common Mistakes:

• Returning right instead of left at base case
• Incorrect mid calculation causing infinite loop
• Misplaced recursive calls

5. Suppose the problem is modified so that the array can contain multiple identical adjacent elements (plateaus), and you want to find any peak element efficiently. Which modification to the original modified binary search algorithm correctly handles this scenario without degrading to linear time?

hard

A. Change the comparison to nums[mid] <= nums[mid + 1] and recurse right if true, else left

B. Skip over equal adjacent elements by moving mid until nums[mid] != nums[mid + 1] before comparison

C. Use linear scan since binary search cannot handle plateaus correctly

D. Modify recursion to always recurse left half to find the first peak

Solution

1. Step 1: Understand plateau challenge

   Equal adjacent elements break strict inequality assumptions in original binary search.

2. Step 2: Modify comparison to handle equality

   Using ≤ ensures recursion moves right when plateau or increasing slope, preserving O(log n) time.

3. Step 3: Avoid linear scan or skipping elements

   Skipping elements or linear scan can degrade performance; always recursing left loses efficiency.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Modified comparison handles plateaus without extra overhead [OK]

Hint: Use <= comparison to handle plateaus in binary search [OK]

Common Mistakes:

• Trying to skip equal elements linearly
• Assuming linear scan is necessary
• Always recursing one side losing log n guarantee