Problem overview
Koko has several piles of bananas, piles[i] in pile i, and the guards return in h hours. She picks a speed k, in bananas per hour. Each hour she chooses one pile and eats up to k bananas from it. If the pile has fewer than k, she finishes it and wastes the rest of that hour. A pile of p bananas therefore takes p / k hours, rounded up. The method minEatingSpeed returns the smallest integer speed that finishes everything within h hours.
With piles = [3, 6, 7, 11] and h = 8, the answer is 4. At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours. At speed 3 they take 1 + 2 + 3 + 4 = 10 hours, which is too many. With piles = [30, 11, 23, 4, 20] and h = 5 there are as many hours as piles, so each pile must go in one hour and the speed is the biggest pile, 30. With h = 6 the answer drops to 23.
The statement asks for O(n log m) time, where m is the biggest pile, and O(1) extra space.
Approach: binary search on the speed
The simple idea is to try speeds 1, 2, 3 and so on until one works. Piles can hold up to a billion bananas, so that can mean a billion attempts, each looking at every pile.
The way out is to notice a pattern in the answers. If Koko finishes in time at speed k, she also finishes at any faster speed. If she doesn't finish at k, no slower speed works either. For the first example, the total hours at each speed are:
k=1 hours=27
k=2 hours=15
k=3 hours=10
k=4 hours=8
k=5 hours=8
k=6 hours=6
k=7 hours=5
k=8 hours=5
k=9 hours=5
k=10 hours=5
k=11 hours=4
The hours never go up as the speed rises, so the speeds split into "too slow" followed by "fast enough", and the answer is the first speed of the second group (4 here, the first speed with 8 hours or fewer). A sorted list with a single switch point is exactly what binary search finds, even though no list of speeds is stored. This technique is called binary search on the answer.
The search range runs from 1 to the biggest pile. The biggest pile always works: at that speed every pile takes one hour, and the constraints guarantee n <= h, so there are never more piles than hours. No answer is ever bigger, and none is smaller than 1. Each check, computing the total hours for one speed, costs O(n), and the search needs about log2(m) checks, which gives O(n log m).
Step by step
- Set the range.
leftis 1, the slowest speed, andrightstarts atpiles[0]. The next two steps raise it to the biggest pile. - Loop over the piles with a for-each loop and set
righttoMath.max(right, pile). After the loop,rightis the biggest pile. - Store a safe answer.
answerstarts atright, a speed known to work, so there is a valid result before the search starts. - Loop while
left <= right. When both are equal, one speed is still untried. - Pick a speed halfway:
k = left + (right - left) / 2. - Test it with a helper,
hours(piles, k), which returns the total hours as along. You write it after this method. - If the hours are at most
h, speedkworks. Save it inanswerfirst, because it may be the smallest, then setright = k - 1to look for a slower speed. - Otherwise
kis too slow, and so is everything below it, so setleft = k + 1. - Return
answer. When the loop ends, every speed below it was too slow. - Write
hours. It declares along totalstarting at 0, loops over the piles and adds the hours of each pile. It returnstotal. - Round up with integers only. The hours for a pile are
(pile + k - 1) / k. For a pile of 7 at speed 3,7 / 3is 2 and forgets the last hour, while(7 + 2) / 3is 3. For an exact multiple such as 6,(6 + 2) / 3is still 2, because addingk - 1never reaches the next multiple.
The solution in Java
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1, right = piles[0];
for (int pile : piles) {
right = Math.max(right, pile);
}
int answer = right;
while (left <= right) {
int k = left + (right - left) / 2;
if (hours(piles, k) <= h) {
answer = k;
right = k - 1;
} else {
left = k + 1;
}
}
return answer;
}
long hours(int[] piles, int k) {
long total = 0;
for (int pile : piles) {
total += (pile + k - 1) / k;
}
return total;
}
}
Details worth knowing:
- Why
hoursreturns along. At speed 1, 10,000 piles of 1,000,000,000 bananas take 10,000,000,000,000 hours, far beyond the 32-bitintmaximum of 2,147,483,647. Adding those piles into aninttotal wraps silently: the same sum, computed with aninttotal, ends as1316134912, while alongtotal gives10000000000000. A wrapped total could even come out smaller thanhand make a hopeless speed look fine. - The sum
pile + k - 1stays anint. That is safe here: both values are at most 1,000,000,000, so the sum is below 2,147,483,647. Only the running total needs along. Adding anintto alongwith+=widens it automatically. - A helper without
public.hoursbelongs to the class and is used only byminEatingSpeed, so it needs no modifier. - Comparing
longwithint. Inhours(piles, k) <= h, Java widenshtolongbefore comparing, so no cast is needed.
Complexity
Time: O(n log m). Finding the biggest pile takes O(n). The search then runs about log2(m) times, around 30 for a billion, and each pass calls hours, which loops over the n piles.
Space: O(1). The method keeps a handful of numbers.
Edge cases and common mistakes
- One pile.
[312884470]withh = 312884469gives 2, and[1000000000]withh = 2gives 500000000. Withh = 1, a pile of 5 needs speed 5. - As many hours as piles. The answer is the biggest pile. With
[1, 1, 1]andh = 3it is 1. - Forgetting to round up. Plain
pile / kdrops the last, partial hour, so the method reports speeds that are too slow. - An
inttotal. It overflows on large inputs, as shown above. With 10,000 piles of 1,000,000,000 andh = 10000, the correct answer is 1000000000. - Not saving
kbefore movingright. The search never comes back tok, so the value would be lost. - Starting
leftat 0. Speed 0 would divide by zero inhours.
Testing
piles = [3, 6, 7, 11],h = 8gives4.piles = [30, 11, 23, 4, 20],h = 5gives30.piles = [30, 11, 23, 4, 20],h = 6gives23.piles = [312884470],h = 312884469gives2.piles = [5],h = 1gives5.
