875. Koko Eating Bananas - Explanation

Description

You are given an integer array piles where piles[i] is the number of bananas in the ith pile. You are also given an integer h, which represents the number of hours you have to eat all the bananas.

You may decide your bananas-per-hour eating rate of k. Each hour, you may choose a pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, you may finish eating the pile but you can not eat from another pile in the same hour.

Return the minimum integer k such that you can eat all the bananas within h hours.

Example 1:

Input: piles = [1,4,3,2], h = 9

Output: 2

Explanation: With an eating rate of 2, you can eat the bananas in 6 hours. With an eating rate of 1, you would need 10 hours to eat all the bananas (which exceeds h=9), thus the minimum eating rate is 2.

Example 2:

Input: piles = [25,10,23,4], h = 4

Output: 25

Constraints:

1 <= piles.length <= 1,000
piles.length <= h <= 1,000,000
1 <= piles[i] <= 1,000,000,000

Topics

Array Binary Search

Recommended Time & Space Complexity

You should aim for a solution with O(nlogm) time and O(1) space, where n is the size of the input array, and m is the maximum value in the array.

Hint 1

Given h is always greater than or equal to the length of piles, can you determine the upper bound for the answer? How much time does it take Koko to eat a pile with x bananas?

Hint 2

It takes ceil(x / k) time to finish the x pile when Koko eats at a rate of k bananas per hour. Our task is to determine the minimum possible value of k. However, we must also ensure that at this rate, k, Koko can finish eating all the piles within the given h hours. Can you now think of the upper bound for k?

Hint 3

The upper bound for k is the maximum size of all the piles. Why? Because if Koko eats the largest pile in one hour, then it is straightforward that she can eat any other pile in an hour only.

Hint 4

Consider m to be the largest pile and n to be the number of piles. A brute force solution would be to linearly check all values from 1 to m and find the minimum possible value at which Koko can complete the task. This approach would take O(n * m) time. Can you think of a more efficient method? Perhaps an efficient searching algorithm could help.

Hint 5

Rather than linearly scanning, we can use binary search. The upper bound of k is max(piles) and since we are only dealing with positive values, the lower bound is 1. The search space of our binary search is 1 through max(piles). This allows us to find the smallest possible k using binary search.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Search - The optimal solution uses binary search on the answer space to find the minimum valid eating speed
Search Space Reduction - Understanding how to identify monotonic properties that allow binary search on a range of possible answers
Ceiling Division - Calculating hours per pile requires rounding up, which is essential for correct time computation

1. Brute Force

Intuition

We try every possible eating speed starting from 1.
For each speed, we simulate how many hours it would take to finish all piles.
The first speed that finishes within h hours is the answer.

Algorithm

Start with speed = 1.
For each speed:
- Compute the total hours needed by summing ceil(pile / speed) for every pile.
If the total hours is less than or equal to h, return the current speed.
Otherwise, increase the speed and repeat.

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        speed = 1
        while True:
            totalTime = 0
            for pile in piles:
                totalTime += math.ceil(pile / speed)

            if totalTime <= h:
                return speed
            speed += 1
        return speed

public class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int speed = 1;
        while (true) {
            long totalTime = 0;
            for (int pile : piles) {
                totalTime += (int) Math.ceil((double) pile / speed);
            }

            if (totalTime <= h) {
                return speed;
            }
            speed++;
        }
    }
}

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int speed = 1;
        while (true) {
            long long totalTime = 0;
            for (int pile : piles) {
                totalTime += (pile + speed - 1) / speed;
            }

            if (totalTime <= h) {
                return speed;
            }
            speed++;
        }
    }
};

class Solution {
    /**
     * @param {number[]} piles
     * @param {number} h
     * @return {number}
     */
    minEatingSpeed(piles, h) {
        let speed = 1;
        while (true) {
            let totalTime = 0;
            for (let pile of piles) {
                totalTime += Math.ceil(pile / speed);
            }

            if (totalTime <= h) {
                return speed;
            }
            speed++;
        }
    }
}

public class Solution {
    public int MinEatingSpeed(int[] piles, int h) {
        int speed = 1;
        while (true) {
            long totalTime = 0;
            foreach (int pile in piles) {
                totalTime += (int) Math.Ceiling((double) pile / speed);
            }

            if (totalTime <= h) {
                return speed;
            }
            speed++;
        }
    }
}

func minEatingSpeed(piles []int, h int) int {
   speed := 1
   for {
       totalTime := 0
       for _, pile := range piles {
           totalTime += int(math.Ceil(float64(pile) / float64(speed)))
       }

       if totalTime <= h {
           return speed
       }
       speed += 1
   }
   return speed
}

class Solution {
    fun minEatingSpeed(piles: IntArray, h: Int): Int {
        var speed = 1
        while (true) {
            var totalTime = 0L
            for (pile in piles) {
                totalTime += Math.ceil(pile.toDouble() / speed).toLong()
            }

            if (totalTime <= h) {
                return speed
            }
            speed += 1
        }
        return speed
    }
}

class Solution {
    func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
        var speed = 1

        while true {
            var totalTime = 0
            for pile in piles {
                totalTime += Int(ceil(Double(pile) / Double(speed)))
            }

            if totalTime <= h {
                return speed
            }
            speed += 1
        }
        return speed
    }
}

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(1)$

Where $n$ is the length of the input array $piles$ and $m$ is the maximum number of bananas in a pile.

2. Binary Search

Intuition

Instead of checking every speed one by one, we notice that the total time needed decreases as the eating speed increases.
This means the answer lies in a sorted search space from 1 to max(piles).

Because the search space is ordered, we can use binary search to efficiently find the smallest speed that allows finishing the piles within h hours.

Algorithm

Set the search range:
- left = 1 (minimum possible speed)
- right = max(piles) (maximum needed speed)
While left <= right:
- Let mid be the current speed to test.
- Compute the total hours needed using this speed.
If the total hours is within the allowed time h:
- This speed works, so record it.
- Try to find a smaller working speed by searching the left half.
Otherwise:
- Speed is too slow, so search in the right half.
After the search ends, return the smallest valid speed found.

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        res = r

        while l <= r:
            k = (l + r) // 2

            totalTime = 0
            for p in piles:
                totalTime += math.ceil(float(p) / k)
            if totalTime <= h:
                res = k
                r = k - 1
            else:
                l = k + 1
        return res

public class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1;
        int r = Arrays.stream(piles).max().getAsInt();
        int res = r;

        while (l <= r) {
            int k = (l + r) / 2;

            long totalTime = 0;
            for (int p : piles) {
                totalTime += Math.ceil((double) p / k);
            }
            if (totalTime <= h) {
                res = k;
                r = k - 1;
            } else {
                l = k + 1;
            }
        }
        return res;
    }
}

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int l = 1;
        int r = *max_element(piles.begin(), piles.end());
        int res = r;

        while (l <= r) {
            int k = (l + r) / 2;

            long long totalTime = 0;
            for (int p : piles) {
                totalTime += ceil(static_cast<double>(p) / k);
            }
            if (totalTime <= h) {
                res = k;
                r = k - 1;
            } else {
                l = k + 1;
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} piles
     * @param {number} h
     * @return {number}
     */
    minEatingSpeed(piles, h) {
        let l = 1;
        let r = Math.max(...piles);
        let res = r;

        while (l <= r) {
            const k = Math.floor((l + r) / 2);

            let totalTime = 0;
            for (const p of piles) {
                totalTime += Math.ceil(p / k);
            }
            if (totalTime <= h) {
                res = k;
                r = k - 1;
            } else {
                l = k + 1;
            }
        }
        return res;
    }
}

public class Solution {
    public int MinEatingSpeed(int[] piles, int h) {
        int l = 1;
        int r = piles.Max();
        int res = r;

        while (l <= r) {
            int k = (l + r) / 2;

            long totalTime = 0;
            foreach (int p in piles) {
                totalTime += (int)Math.Ceiling((double)p / k);
            }
            if (totalTime <= h) {
                res = k;
                r = k - 1;
            } else {
                l = k + 1;
            }
        }
        return res;
    }
}

func minEatingSpeed(piles []int, h int) int {
   l, r := 1, 0
   for _, p := range piles {
       if p > r {
           r = p
       }
   }
   res := r

   for l <= r {
       k := (l + r) / 2
       totalTime := 0

       for _, p := range piles {
           totalTime += int(math.Ceil(float64(p) / float64(k)))
       }

       if totalTime <= h {
           res = k
           r = k - 1
       } else {
           l = k + 1
       }
   }
   return res
}

class Solution {
    fun minEatingSpeed(piles: IntArray, h: Int): Int {
        var l = 1
        var r = piles.max()!!
        var res = r

        while (l <= r) {
            val k = (l + r) / 2
            var totalTime = 0L

            for (p in piles) {
                totalTime += Math.ceil(p.toDouble() / k).toLong()
            }

            if (totalTime <= h) {
                res = k
                r = k - 1
            } else {
                l = k + 1
            }
        }
        return res
    }
}

class Solution {
    func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
        var l = 1, r = piles.max()!
        var res = r

        while l <= r {
            let k = (l + r) / 2

            var totalTime = 0
            for p in piles {
                totalTime += Int(ceil(Double(p) / Double(k)))
            }

            if totalTime <= h {
                res = k
                r = k - 1
            } else {
                l = k + 1
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n * \log m)$
Space complexity: $O(1)$

Where $n$ is the length of the input array $piles$ and $m$ is the maximum number of bananas in a pile.

Common Pitfalls

Using Integer Division Instead of Ceiling

When calculating hours needed per pile, you must round up since Koko spends a full hour even if fewer bananas remain. Using regular integer division gives wrong results.

# Wrong: Integer division rounds down
totalTime += pile // speed

# Correct: Ceiling division
totalTime += math.ceil(pile / speed)
# Or without import:
totalTime += (pile + speed - 1) // speed

Setting Wrong Binary Search Bounds

The minimum speed is 1 (not 0, which would cause division by zero). The maximum speed needed is max(piles) since eating faster than the largest pile provides no benefit.

# Wrong: Starting from 0
l = 0  # Division by zero!

# Wrong: Arbitrary upper bound
r = sum(piles)  # Unnecessarily large

# Correct bounds
l, r = 1, max(piles)

Integer Overflow in Total Time

When summing hours across all piles, the total can exceed 32-bit integer limits for large inputs. Use a long integer type in languages like Java/C++.

// Wrong: May overflow
int totalTime = 0;

// Correct: Use long
long totalTime = 0;