What is the time and space complexity of Koko Eating Bananas?

Time complexity: O(n log m) where m is max pile. Space complexity: O(1).

Koko Eating Bananas

Med

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Koko Eating Bananas

Approach

Binary search on the eating speed from 1 to max(piles). For each candidate speed, compute total hours needed by summing ceil(pile/speed). If total hours fits within h, try a slower speed. Otherwise increase.

Complexity Analysis

Time: O(n log m) where m is max pile
Space: O(1)

Pattern

Binary Search on Answer

Why It Works

If Koko can finish at speed k, she can also finish at speed k+1 (monotonic). Binary search the speed from 1 to max(piles), checking feasibility each time.

Updated Mar 2026