Difficulty: Medium · LeetCode 875

Problem

Koko can decide her eating speed k per hour. Return minimum integer k such that she can eat all bananas within h hours.

Understanding the problem

The answer space of speeds $k \in [1, \max(\text{piles})]$ is monotonic: if speed $k$ is valid, all speeds $> k$ are also valid.

Intuition

Binary search on the answer space range $[1, \max(\text{piles})]$. Find the first speed where total hours $\le h$.

Approach

Set left = 1, right = max(piles).
Loop while left <= right:
Set speed = left + (right - left) // 2.
Compute hours = sum((pile + speed - 1) // speed for pile in piles).
If hours <= h: speed is valid! Record answer = speed and try smaller speeds right = speed - 1.
Else: speed is too slow, try faster speeds left = speed + 1.

Naive Solution — Brute Force

Linear search trying every speed $k = 1, 2, 3 \dots \max(\text{piles})$ and checking total hours.

Python

class Solution:
    def minEatingSpeed(self, piles, h):

        for speed in range(1, max(piles) + 1):

            hours = 0

            for pile in piles:
                hours += (
                    pile + speed - 1
                ) // speed

            if hours <= h:
                return speed

        return max(piles)

C++

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

        for (int speed = 1; speed <= maxPile; speed++) {
            long long hours = 0;

            for (int pile : piles) {
                hours += ((long long) pile + speed - 1) / speed;
            }

            if (hours <= h) {
                return speed;
            }
        }

        return maxPile;
    }
};

Java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int maxPile = 0;
        for (int pile : piles) {
            maxPile = Math.max(maxPile, pile);
        }

        for (int speed = 1; speed <= maxPile; speed++) {
            long hours = 0;

            for (int pile : piles) {
                hours += ((long) pile + speed - 1) / speed;
            }

            if (hours <= h) {
                return speed;
            }
        }

        return maxPile;
    }
}

JavaScript

var minEatingSpeed = function(piles, h) {
    const maxPile = Math.max(...piles);

    for (let speed = 1; speed <= maxPile; speed++) {
        let hours = 0;

        for (const pile of piles) {
            hours += Math.floor((pile + speed - 1) / speed);
        }

        if (hours <= h) {
            return speed;
        }
    }

    return maxPile;
};

Time: O(n × max(piles)) · Space: O(1)

Optimized Code (Python 3)

Python

class Solution:
    def minEatingSpeed(self, piles, h):

        left = 1
        right = max(piles)

        answer = right

        while left <= right:
            speed = left + (right - left) // 2

            hours = 0

            for pile in piles:
                hours += (
                    pile + speed - 1
                ) // speed

            if hours <= h:
                answer = speed
                right = speed - 1
            else:
                left = speed + 1

        return answer

C++

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

        int answer = right;

        while (left <= right) {
            int speed = left + (right - left) / 2;

            long long hours = 0;

            for (int pile : piles) {
                hours += ((long long) pile + speed - 1) / speed;
            }

            if (hours <= h) {
                answer = speed;
                right = speed - 1;
            } else {
                left = speed + 1;
            }
        }

        return answer;
    }
};

Java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }

        int answer = right;

        while (left <= right) {
            int speed = left + (right - left) / 2;

            long hours = 0;

            for (int pile : piles) {
                hours += ((long) pile + speed - 1) / speed;
            }

            if (hours <= h) {
                answer = speed;
                right = speed - 1;
            } else {
                left = speed + 1;
            }
        }

        return answer;
    }
}

JavaScript

var minEatingSpeed = function(piles, h) {
    let left = 1;
    let right = Math.max(...piles);

    let answer = right;

    while (left <= right) {
        const speed = left + Math.floor((right - left) / 2);

        let hours = 0;

        for (const pile of piles) {
            hours += Math.floor((pile + speed - 1) / speed);
        }

        if (hours <= h) {
            answer = speed;
            right = speed - 1;
        } else {
            left = speed + 1;
        }
    }

    return answer;
};

Time: O(n log(max(piles))) · Space: O(1)

Takeaway

Pattern — Monotonic feasibility condition → Binary Search on Answer