Koko Eating Bananas

Koko Eating Bananas is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Answer / Condition Function subpattern.

Problem statement

Koko loves to eat bananas. There are n piles of bananas, the ith 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.

Example 1:

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

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 <= 104

- piles.length <= h <= 109

- 1 <= piles[i] <= 109

Topics and companies

Topics: Array, Binary Search.

Reported in interviews at Airbnb, Amazon, Facebook, Google.

How to practise Koko Eating Bananas on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * log M), where n is the number of piles and M is the maximum number of bananas in any pile. The binary search runs in O(log M) and for each candidate k, we scan all n piles. time and O(1) extra space (excluding input). Only a few integer variables are used. space.

Open Koko Eating Bananas in the code editor, or read the Koko Eating Bananas editorial for a worked solution with its approach and complexity analysis.

Where Koko Eating Bananas sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• On Answer / Condition Function subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Koko Eating Bananas

Other problems that use the same On Answer / Condition Function and Binary Search Patterns techniques:

• Capacity To Ship Packages Within D Days — Medium, same subpattern
• Maximum Candies Allocated to K Children — Medium, same subpattern
• Minimized Maximum of Products Distributed to Any Store — Medium, same subpattern
• Minimize Max Distance to Gas Station — Hard, same subpattern
• Minimum Limit of Balls in a Bag — Medium, same subpattern
• Minimum Number of Days to Make m Bouquets — Medium, same subpattern