DSA Visualizations | Hello Interview

Apple Harvest (Koko Eating Bananas)

DESCRIPTION (credit 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.

EXAMPLES

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)

Run your code to see results here

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:

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 apples in the orchard to run, as we iterate over each apple in apples.

Brute-Force Solution

Here is the brute-force solution to the problem:

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.

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:

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:

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!

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?).

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.

This binary search continues until left and right are equal.

Set mid = (left + right) / 2 = 8 apples per hour.

This is fast enough (T), so we set right = mid.

Set mid = (right + left) / 2.

This is still fast enough (T), so set right = mid.

Now, left = right, our search space only has one element left. We can return the answer as left (or right).

Optimal Solution

class Solution:
    def minHarvestRate(self, apples, h):
        def time_taken(rate):
            time = 0
            for i in range(len(apples)):
                time += (apples[i] + rate - 1) // rate 
            return time

        left, right = 1, max(apples)
        while left < right:
            mid = (left + right) // 2
            if time_taken(mid) > h:
                left = mid + 1
            else:
                right = mid
                
        return left

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.

Next: Search in Rotated Sorted Array

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

Sort By

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Overview

Search in Rotated Sorted Array

Apple Harvest (Koko Eating Bananas)

DESCRIPTION (credit Leetcode.com)

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

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).

EXAMPLES

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)

Run your code to see results here

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:

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 apples in the orchard to run, as we iterate over each apple in apples.

Brute-Force Solution

Here is the brute-force solution to the problem:

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

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.

apples = [4, 7, 9, 12] and h = 6

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:

apples = [4, 7, 9, 12] and h = 6

Reducing Search Space

Let's set up the pointers like we do in classic binary search:

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.

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.

This is fast enough (T), so we set right = mid.

Set mid = (right + left) / 2.

This is still fast enough (T), so set right = mid.

Now, left = right, our search space only has one element left. We can return the answer as left (or right).

Optimal Solution

class Solution:
    def minHarvestRate(self, apples, h):
        def time_taken(rate):
            time = 0
            for i in range(len(apples)):
                time += (apples[i] + rate - 1) // rate 
            return time

        left, right = 1, max(apples)
        while left < right:
            mid = (left + right) // 2
            if time_taken(mid) > h:
                left = mid + 1
            else:
                right = mid
                
        return left

Complexity Analysis

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

Next: Search in Rotated Sorted Array

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

Sort By

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA Guided Practice Hello Interview Premium

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103