LeetCode 875 - Koko Eating Bananas

LeetCode Problem 875

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem asks us to determine the minimum eating speed k for Koko such that she can finish all piles of bananas within a given number of hours h. The input consists of an array piles, where piles[i] represents the number of bananas in the ith pile, and an integer h which indicates the maximum hours available. The output is a single integer k, representing the minimum number of bananas per hour Koko must eat to finish all piles in h hours.

Key points to understand: each hour, Koko chooses a pile and eats exactly k bananas or the remainder of the pile if fewer than k bananas are left. She cannot split her eating across multiple piles in one hour. The constraints show that both the number of piles and the number of bananas per pile can be very large, up to 10^4 piles and 10^9 bananas. Also, the number of hours h can be as large as 10^9. This indicates that a brute-force solution iterating over every possible k would be too slow, and we must find an efficient search method.

Edge cases include: if h equals the number of piles, Koko must eat the largest pile in one hour; if h is extremely large, she can eat very slowly; and when all piles have equal bananas, the solution is trivial but should not break the algorithm.

Approaches

A brute-force approach would try every possible k from 1 up to the maximum number of bananas in a pile. For each k, we compute the total hours needed by summing the ceiling of pile / k for all piles. The first k that allows Koko to finish within h hours is the answer. While correct, this is inefficient because the maximum pile size can be up to 10^9, resulting in up to a billion iterations.

The optimal approach leverages a binary search over the range of possible eating speeds. The key observation is that the total hours required is monotonically decreasing with increasing k. If Koko can finish eating all bananas at speed k, she can also finish at any higher speed. Conversely, if she cannot finish at k, she cannot finish at any lower speed. This property allows us to apply binary search over k to efficiently find the minimal viable speed.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(max(piles) * n)	O(1)	Iterates every possible k from 1 to max pile size and sums hours
Optimal	O(n * log(max(piles)))	O(1)	Binary search over eating speed; sum hours for each candidate

Algorithm Walkthrough

1. Initialize the search range for k with low = 1 and high = max(piles). low represents the minimum possible speed, and high the maximum pile size.
2. While low < high, compute the middle speed mid = low + (high - low) // 2.
3. Calculate the total hours needed at speed mid by iterating over each pile and summing ceil(pile / mid).
4. If the total hours is less than or equal to h, it means Koko can eat at this speed or slower, so adjust the upper bound high = mid.
5. Otherwise, Koko cannot finish at this speed, so increase the lower bound low = mid + 1.
6. When the loop finishes, low equals high, which is the minimal speed k allowing Koko to finish within h hours.

Why it works: The algorithm maintains the invariant that the minimum feasible speed lies within [low, high]. By repeatedly narrowing the range based on whether the current mid speed allows finishing on time, binary search guarantees convergence to the minimum viable k.

Python Solution

from typing import List
import math

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def hours_needed(speed: int) -> int:
            total_hours = 0
            for pile in piles:
                total_hours += math.ceil(pile / speed)
            return total_hours
        
        low, high = 1, max(piles)
        
        while low < high:
            mid = low + (high - low) // 2
            if hours_needed(mid) <= h:
                high = mid
            else:
                low = mid + 1
        
        return low

The function hours_needed computes the total hours Koko needs for a given speed. The main loop performs binary search over the range of speeds. If hours_needed(mid) is within the limit h, we know we can potentially lower the speed, so we reduce high. Otherwise, we increase low. The final value of low is the minimum speed satisfying the constraints.

Go Solution

import "math"

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

    low, high := 1, 0
    for _, pile := range piles {
        if pile > high {
            high = pile
        }
    }

    for low < high {
        mid := low + (high - low) / 2
        if hoursNeeded(mid) <= h {
            high = mid
        } else {
            low = mid + 1
        }
    }
    return low
}

In Go, we use a closure hoursNeeded to calculate the required hours. We initialize high by scanning the piles to find the maximum. We use integer division carefully and convert values to float64 for the ceiling operation. The binary search logic mirrors the Python implementation.

Worked Examples

Example 1: piles = [3,6,7,11], h = 8

Iteration	mid	hours_needed(mid)	low	high
1	6	5	1	6
2	3	9	4	6
3	5	6	4	5
4	4	8	4	4

Result: 4

Example 2: piles = [30,11,23,4,20], h = 5

Iteration	mid	hours_needed(mid)	low	high
1	25	6	26	30
2	28	5	26	28
3	27	5	26	27
4	26	6	27	27
5	30	5	30	30

Result: 30

Example 3: piles = [30,11,23,4,20], h = 6

Iteration	mid	hours_needed(mid)	low	high
1	15	10	16	30
2	23	6	16	23
3	19	7	20	23
4	21	6	20	21
5	20	7	21	21
6	23	6	21	23
7	22	6	21	22
8	21	6	21	21

Result: 23

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * log m)	n piles and binary search over m = max(piles)
Space	O(1)	Only constant extra space is used

The binary search reduces the candidate speeds from max(piles) to log(max(piles)) steps, and each step requires iterating over all piles to sum hours.

Test Cases

# Provided examples
assert Solution().minEatingSpeed([3,6,7,11], 8) == 4  # example 1
assert Solution().minEatingSpeed([30,11,23,4,20], 5) == 30  # example 2
assert Solution().minEatingSpeed([30,11,23,4,20], 6) == 23  # example 3

# Edge cases
assert Solution().minEatingSpeed([1], 1) == 1  # single pile, single hour
assert Solution().minEatingSpeed([1000000000], 2) == 500000000  # large single pile
assert Solution().minEatingSpeed([1]*10000, 10000) == 1  # many piles, exactly one hour per pile
assert Solution().minEatingSpeed([1]*10000, 1) == 10000  # must eat all in one hour
assert Solution().minEatingSpeed([5,10,15], 5) ==