Koko eats bananas at speed k per hour, from one pile per hour. Find the smallest k that lets her finish all piles within h hours.
DSA Animator › DSA Revision › Binary Search › Koko Eating Bananas
Remember: when a yes stays yes as the value grows, binary search the answer. The check function decides which half to keep. The video solves Koko Eating Bananas (LeetCode 875, Medium) with the Binary Search on Answer pattern from the Binary Search topic, and you can replay every step in the interactive Koko Eating Bananas animation.
Koko eats bananas at speed k per hour, from one pile per hour. Find the smallest k that lets her finish all piles within h hours.
For piles 3, 6, 7, 11 and 8 hours, the answer is 4.
Trying every speed from 1 to the biggest pile is O of n times max. But if a speed works, every faster speed also works.
That makes the answer space sorted: too slow, then fast enough. Binary search the speed between 1 and the largest pile. For each guess, the hours needed is the sum of each pile divided by k, rounded up.
Speed 6 takes 1 plus 1 plus 2 plus 2, which is 6 hours, so it works, and we try slower. Speed 3 takes 10 hours, which is too slow, so we go faster. Speed 5 takes 8 hours, so it works. Speed 4 also takes exactly 8 hours, so it works too. The range closes at 4, so the answer is 4.
In code, low is 1 and high is the biggest pile. If the hours at mid fit within h, keep mid as a candidate by moving high to mid. Otherwise move low to mid plus 1. It's O of n log max time and O of 1 space.
Remember: when a yes stays yes as the value grows, binary search the answer. The check function decides which half to keep.