Get Premium
Binary Search

Apple Harvest (Koko Eating Bananas)

medium
DESCRIPTION (inspired by Leetcode.com)

Bobby has an orchard of apple trees, and each tree has a certain number of apples on it.

Bobby wants to collect all the apples by the end of the day by collecting a fixed number of apples per hour. He can only harvest apples from one tree per hour - if he finishes collecting apples from a tree before the hour is up, he must wait until the next hour to move to the next tree.

  • For example, if there are 3 apples on a tree and Bobby collects 1 apple per hour, it will take him 3 hours to finish collecting the apples on that tree.
  • If he harvests 2 apples per hour, it will take him 2 hours to finish collecting all the apples on that tree (he waits until the hour is up even though he finishes early).

Write a function to determine the slowest rate of apples Bobby can harvest per hour to finish the job in at most 'h' hours. The input to the function is an array of integers representing the number of apples on each tree and an integer 'h' representing the number of hours Bobby has to finish the job within.

Example 1:

Input:

apples = [3, 6, 7], h = 8

Output: 3

Explanation:

  • 1 apple per hour: 3 hours for first tree, 6 hours the second tree, and 7 hours for third tree. This totals 16 hours, which is more than the 8 hours he has to finish the job. NOT VALID.
  • 2 apples per hour: 2 + 3 + 4 = 9 hours, which is more than the 8 hours he has to finish the job. NOT VALID.
  • 3 apples per hour: 1 + 2 + 3 = 6 hours, which is less than the 8 hours he has to finish the job. VALID.
  • 4 apples per hour: 1 + 2 + 2 = 5 hours, which is less than the 8 hours he has to finish the job. VALID.
  • 5 apples per hour: 1 + 2 + 2 = 5 hours, which is less than the 8 hours he has to finish the job. VALID.

Therefore, the minimum number of apples Bobby must harvest per hour to finish the job in 8 hours or less is 3.

Example 2:

Input:

apples = [25, 9, 23, 8, 3], h = 5

Output: 25 (Bobby must harvest 25 apples per hour to finish in 5 hours or less)

Explanation

In this problem, we are trying to find the slowest rate at reach we can harvest all the apples in the orchard within the given time limit and the requirements of the problem.

Brute-Force Approach

One observation before starting to solve this problem:
  • The slowest rate at which can harvest apples is 1.
  • The fastest rate at which can harvest apples is equal to the maximum number of apples in the orchard, as going any faster than this will not change the time taken to harvest all the apples.
For example, if apples = [25, 9, 23, 8, 3], then going at rate any faster than 25 apples per hour will take the same time as going at 25 apples per hour.
The brute-force approach to this problem works similar to the explanation in the Example section above.
We'll start with a rate of 1, and calculate the time taken to harvest all the apples at this rate.
  • If that time is less than or equal to the given time limit, then we've found the slowest rate at which we can harvest all the apples in the given time limit, so we return this rate.
  • If the time taken is greater than the given time limit, then we increase the rate by 1 and repeat.

Calculating Time Taken

To calculate the time taken to harvest all the apples at a given rate, we can use this function:
Solution
def time_taken(rate):
    time = 0
    for i in range(len(apples)):
        time += (apples[i] + rate - 1) // rate
    return time
This function takes O(n) where n is the number of trees (the length of the apples array) to run, as we iterate over each tree in apples.

Brute-Force Solution

Here is the brute-force solution to the problem:
Solution
def min_rate(apples, h):
    def time_taken(rate):
        time = 0
        for i in range(len(apples)):
            time += (apples[i] + rate - 1) // rate
        return time
    rate = 1
    while time_taken(rate) > h:
        rate += 1
    return rate
Thus, the total time complexity of the brute-force approach is O(n * (max(apples) - 1)), as we iterate from 1 to the maximum number of apples in the orchard. For each iteration, we calculate the time taken to harvest all the apples using the time_taken function in O(n) time.

Binary Search Approach

One way to visualize all the rates we check in the brute-force approach is like this, shown for when apples = [4, 7, 9, 12] and h = 6.
1234567FFFFFFT
apples = [4, 7, 9, 12] and h = 6
The array on top represents the rate we are trying to harvest apples at, while the array on the bottom represents if that corresponding time is less than or equal to the given time limit h (F for False, T for True). Our brute-force solution returns the rate corresponding to the first T in the bottom array, or 7.
Now let's image our brute-force solution tried everything between 1 and the max_apples in the orchard, instead of returning after the first T. Then the array would look like this:
FFFFFFT123456789101112TTTTT
apples = [4, 7, 9, 12] and h = 6
Why visualize the problem this way? Well, we have a sorted array on top, and a search condition ("find the first T") on the bottom. If we can find a way to eliminate half of the array from our search space at each step, then we can use binary search to solve this problem in O(log(max(apples)) * n) time.

Reducing Search Space

Let's set up the pointers like we do in classic binary search:
FFFFFFT123456789101112TTTTTleftrightmid
apples = [4, 7, 9, 12] and h = 6
At this point, mid points to a rate of 6 apples per hour. This would take 7 hours to harvest all the apples, which is too slow. So we need to reduce our search space.
How should we do it? Well, if 6 apples per hour is already too slow, then anything slower than 6 apples will also be too slow. So we can set left = mid + 1 to discard the left half of the array. Now we're doing binary search!
FFFFFFT123456789101112TTTTTleftrightmid
apples = [4, 7, 9, 12] and h = 6
Next iteration: set mid = (left + right) // 2. Now, mid points to a rate of 9 apples per hour. This would take 5 hours to harvest all the apples, which is fast enough. But can we do better? (i.e. can we find a slower rate that still lets us finish in time?).
FFFFFFT123456789101112TTTTTleftrightmid
apples = [4, 7, 9, 12] and h = 6
We're not sure yet, so let's keep searching. At this point, we can discard the right half of the array by setting right = mid - we know that any rate faster than 9 apples per hour will not be a better answer than 9.
Note how we set right = mid instead of right = mid - 1. This is because mid is still a valid answer, and we don't want to remove it from our search space just yet, like we would if we set it as mid - 1.
FFFFFFT123456789101112TTTTTleftrightmid
apples = [4, 7, 9, 12] and h = 6
This binary search continues until left and right are equal.
  • Set mid = (left + right) / 2 = 8 apples per hour.
FFFFFFT123456789101112TTTTTleftrightmid
  • This is fast enough (T), so we set right = mid.
midFFFFFFT123456789101112TTTTTleftright
  • Set mid = (right + left) / 2.
midFFFFFFT123456781011129TTTTTleftright
  • This is still fast enough (T), so set right = mid.
midFFFFFFT123456781011129TTTTTleftright
Now, left = right, our search space only has one element left. We can return the answer as left (or right).

Optimal Solution

Solution
class Solution:
    def minHarvestRate(self, apples, h):
        # Binary search on harvest rate: find minimum rate to finish in h hours
        def time_taken(rate):
            time = 0
            # Calculate total time needed at this harvest rate
            for i in range(len(apples)):
                # Ceiling division: (apples[i] + rate - 1) // rate
                time += (apples[i] + rate - 1) // rate 
            return time
        # Binary search bounds: minimum rate = 1, maximum rate = max apples
        left, right = 1, max(apples)
        
        # Binary search for minimum valid harvest rate
        while left < right:
            mid = (left + right) // 2
            if time_taken(mid) > h:
                # Rate too slow, need faster rate
                left = mid + 1
            else:
                # Rate is sufficient, try slower rate
                right = mid
                
        return left
Test Your Knowledge

Login to take the complexity quiz and track your progress

Complexity Analysis

Time Complexity: O(log m * n) where m is the maximum number of apples on a tree and n is the number of trees in the apples array. Our binary search runs O(log m) times, and each time it runs it takes n operations to check how long it takes to collect all the apples for that rate.

Space Complexity: O(1) We are using only a constant amount of space.

Mark as read
Next: Search in Rotated Sorted Array

Your account is free and you can post anonymously if you choose.

Questions
Meta SWE Interview QuestionsAmazon SWE Interview QuestionsGoogle SWE Interview QuestionsOpenAI SWE Interview QuestionsAnthropic SWE Interview QuestionsEngineering Manager (EM) Interview Questions
Learn
Learn System DesignLearn DSALearn BehavioralLearn ML System DesignLearn Low Level DesignGuided Practice
Links
FAQPricingGift PremiumHello Interview Premium
Legal
Terms and ConditionsPrivacy PolicySecurity
Contact
About UsProduct Support

7511 Greenwood Ave North Unit #4238 Seattle WA 98103

© 2026 Optick Labs Inc. All rights reserved.

Apple Harvest (Koko Eating Bananas) | Hello Interview