Faangprep Logo
Log inStart free
Browse curriculum

Apple Harvest (Koko Variant)

Find the minimum eating speed to finish all piles within H hours.

Medium
20 min
Solve on LeetCode

Problem Understanding

You have n piles of apples. The i-th pile has piles[i] apples.
You have H hours to eat all apples.

You can decide your eating speed k (apples per hour).

  • Each hour, you choose a pile and eat up to k apples from it.
  • If the pile has less than k apples, you eat them all and stop for that hour (you don't move to the next pile).

Return the minimum integer k such that you can eat all apples within H hours.

Example

  • Piles: [3, 6, 7, 11], H: 8
  • If k=1: Needs 3+6+7+11 = 27 hours (> 8). Too slow.
  • If k=4: Needs 1+2+2+3 = 8 hours (<= 8). Valid.
  • Can we do better? Minimum k is our goal.

Attempt 1: Brute Force (Linear Search on k)

The possible speeds range from k=1 (slowest) to k=max(piles) (fastest - one pile per hour).
We can check every k starting from 1.

  1. Try k=1. Calculate hours. If <= H, return 1.
  2. Try k=2. Calculate hours. If <= H, return 2.
  3. ...

Time Complexity

O(max(P) * n). If max pile is 10^9, this is TLE (Time Limit Exceeded).

The Intuition: Binary Search on Answer

The valid speeds form a monotonic range:

  • If speed k is valid (we finish in time), then any speed > k is also valid (we finish even faster).
  • If speed k is invalid (too slow), then any speed < k is also invalid.

This monotonicity allows us to use Binary Search on the search space of k (from 1 to max(piles)).

  • Range: [1, max(piles)]
  • Mid: Test if speed mid is feasible.
    • If feasible (hours <= H): This mid could be the minimum, but maybe there's a smaller one? Store mid as answer, and search left (high = mid - 1).
    • If not feasible (hours > H): Too slow! Need faster speed. Search right (low = mid + 1).

Interactive Visualization

Step through the search on k and watch each speed’s total hours compared against H.

Dry Run

Piles: [3, 6, 7, 11], H = 8.
Range of k: [1, 11]

Step Low High Mid (k) Hours Calculation Total Hours Condition (<= 8) Action
1 1 11 6 ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 6 6 <= 8 (True) Valid. Ans=6. Try slower. High=5
2 1 5 3 ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4 10 10 <= 8 (False) Too slow. Try faster. Low=4
3 4 5 4 ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 8 8 <= 8 (True) Valid. Ans=4. Try slower. High=3
4 4 3 - Loop Ends - - Return Ans=4

The Solution Template

Binary Search applied to answer range.

Apple Harvest (Koko Variant) Code
1/**
2 * @param {number[]} piles
3 * @param {number} h
4 * @return {number}
5 */
6var minEatingSpeed = function(piles, h) {
7    let low = 1;
8    let high = Math.max(...piles);
9    let ans = high;
10

11    while (low <= high) {
12        let mid = Math.floor(low + (high - low) / 2);
13        let hours = 0;
14        for (let p of piles) {
15            hours += Math.ceil(p / mid);
16        }
17

18        if (hours <= h) {
19            ans = mid;
20            high = mid - 1;
21        } else {
22            low = mid + 1;
23        }
24    }
25    return ans;
26};

Edge Cases

  • n == h: Must eat each pile in 1 hour. k = max(piles).
  • Small piles: k could be small.
  • Large piles: k logic handles up to max value.
  • Integer Overflow: In Java/C++, sum of hours could exceed 2^31, use long.

Summary

This is a classic 'Binary Search on Answer' problem. We search for the optimal parameter 'k' by validating candidates against the constraint 'target hours'.

Previous

Binary Search

Next

Search in Rotated Sorted Array

The approach, step by step

  1. Set the range

    Search speeds from low = 1 to high = max(piles), with answer = max(piles).

  2. Try the middle speed

    For k = the middle of [low, high], add up ceil(pile / k) over every pile.

  3. Keep the half that can hold the answer

    If the total is at most h, record k and set high = k - 1; otherwise set low = k + 1.

  4. Return the answer

    When low passes high, the recorded answer is the slowest speed that finishes.

Frequently asked questions

Why can binary search find the minimum eating speed?

Feasibility is monotonic: if a speed k finishes every pile within h hours, every faster speed does too. That splits the speeds from 1 to max(piles) into a failing range and a passing range, and binary search finds where they meet.

How are the hours for a speed k calculated?

Each pile takes ceil(pile / k) hours, because a partly eaten pile still uses the whole hour. The integer form (pile + k - 1) / k avoids floating point, and the total should be held in a 64-bit integer when piles are large.

What is the time complexity of Koko Eating Bananas?

O(n log M), where n is the number of piles and M is the largest pile: about log M speeds are tried and each costs one pass over the piles. The extra space is O(1).

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description