Koko Eating Bananas

Problem

Koko has piles of bananas and h hours to eat them. In each hour she chooses one pile and eats k bananas from it. If the pile has fewer than k bananas, she finishes that pile and stops for the hour.

Return the minimum integer eating speed k so that she can finish all piles within h hours.

Intuition

This is not a search for a value inside an array. It is a search for the smallest speed that makes a predicate true.

Define:

can_finish(k) = "Koko can eat all bananas within h hours at speed k"

That predicate is monotone:

• if can_finish(k) is true, then can_finish(k + 1) is also true;
• if can_finish(k) is false, every smaller speed is also false.

Monotonicity is the only thing binary search needs. Once you see it, the algorithm writes itself.

Approach

impl Solution {
    pub fn min_eating_speed(piles: Vec<i32>, h: i32) -> i32 {
        let mut lo: i64 = 1;
        let mut hi: i64 = *piles.iter().max().unwrap() as i64;
        let h = h as i64;

        while lo < hi {
            let mid= lo + (hi - lo) / 2;
            let hours: i64= piles
                .iter()
                .map(|&pile| ((pile as i64) + mid - 1) / mid)
                .sum();

            if hours <= h {
                hi= mid;
            } else {
                lo= mid + 1;
            }
        }

        lo as i32
    }
}

function minEatingSpeed(piles: number[], h: number): number {
  let lo = 1;
  let hi = 0;
  for (const pile of piles) {
    if (pile > hi) hi = pile;
  }

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    let hours = 0;

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

    if (hours <= h) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }

  return lo;
}

Trace

For piles = [3, 6, 7, 11] and h = 8:

The search converges on speed 4, which is the smallest feasible value.

Edge cases

• h == piles.len() — Koko must finish one pile per hour, so the answer is max(piles).
• Very large piles — the predicate still works because the complexity depends on log(maxPile), not the pile magnitudes themselves.
• Ceiling division — use integer arithmetic; floating point is unnecessary and less precise.

Takeaway

Binary search on answer is just lower-bound search over a monotone feasibility check. The data structure may disappear completely; what remains is a proof that "bigger is never worse" or "smaller is never worse."

This is the jump from toy binary search to real optimization problems.