Leetcode: minEatingSpeed

Jennifer — Wed, 28 Aug 2024 02:18:08 +0000

Breaking Down Leetcode Problems: Koko Eating Bananas

Hi, welcome to my new series where I break down Leetcode problems to help you understand the thought process. Let's dive straight into the problem.

The Problem

Koko loves to eat bananas. There are n piles of bananas, where the ith pile has piles[i] bananas. The guards have left and will return in h hours.

Koko can decide her bananas-per-hour eating speed, denoted by k. Each hour, she chooses a pile and eats k bananas. If the pile has fewer than k bananas, she eats all of them and does not eat any more bananas during that hour.

Your task is to return the minimum integer k such that Koko can eat all the bananas within h hours.

Let's Break It Down

I admit, this problem took me some time to understand due to its wording.

You are given an array of integers piles, where each element represents a pile of bananas. You are also given h, the total number of hours Koko has to eat all the bananas. Your goal is to find the minimum speed k at which Koko needs to eat to finish all the bananas within the given hours (h).

The problem also tells us that a pile of bananas (piles[i]) could be smaller than Koko's eating speed (meaning she might eat faster than the number of bananas in a pile).

Sample Input

Let's look at a sample input:

Input: piles = [3, 6, 7, 11], h = 8
Output: 4

We need to find the minimum speed k, which can range from 1 to the maximum number in the array (11 in this example).

Approach

To solve the problem, we need to find the minimum speed that allows Koko to eat all the bananas within h hours. Since we don't know k, we can use binary search:

Guess k: Start with a midpoint in the range (1 to max(piles)) and calculate the total hours required to eat all piles at that speed (curr_h).
Adjust the Range:
- If curr_h > h, k is too small. Increase k by setting low to k + 1.
- If curr_h <= h, k might be sufficient. Decrease k by setting high to k - 1.

Solution Code

Here's the Python implementation:


python
from math import ceil

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)

    while low <= high:
        k = (low + high) // 2
        curr_h = sum(ceil(pile / k) for pile in piles)

        if curr_h > h:
            low = k + 1
        else:
            high = k - 1

    return low