Where it runs
1. The problem
You have a line of tasks that take [7, 2, 5, 10, 8] hours, and 2 workers. You must cut the line into 2 chunks, keeping the tasks in order, and give one chunk to each worker. You want the busiest worker's day to be as short as possible.
There is no sorted array to search here. The question is: what is the shortest "longest shift" you can get? Trying every way to cut the line gets huge fast once there are many tasks.
Another question is easy to answer: "can you cut the line so that no shift is longer than 18 hours?" That is a yes/no check, and one pass over the tasks answers it. The limits come in order, too: if 18 works, then 19, 20 and any bigger number work as well. That order is enough to find the answer itself with binary search.
2. In plain words
Try a limit of 15 hours per worker on the tasks [7, 2, 5, 10, 8]. The first worker takes 7, 2 and 5, which is 14 hours. The 10-hour task no longer fits with them, so the second worker takes it. The 8-hour task doesn't fit with the second worker either: 10 + 8 = 18. You would need a third worker, and there are only two. So 15 doesn't work.
Now try a limit of 21. The first worker takes 7, 2 and 5 (14 hours), the second takes 10 and 8 (18 hours). Two workers are enough, so 21 works.
So the answer is above 15 and at most 21. From here you halve that range, as in ordinary binary search. A limit that doesn't work means: try bigger. A limit that works means: try smaller. After a few checks, the smallest limit that still works is left. Here it is 18.
3. The idea
Write a "does it fit" check. Pick a cap: the largest sum one chunk is allowed to reach. Ask whether the line can be cut into k chunks so that each stays within that limit. The check is greedy. Walk the tasks and keep the sum of the current chunk. If the next task would push the sum past cap, start a new chunk. At the end, count the chunks. If there are k or fewer, this cap works. Call this check feasible(cap).
The check is monotonic: a bigger cap never needs more chunks. So once some cap works, every bigger one works too. That gives the same false, false, ..., true, true shape as the boundary search. The difference: now you search among possible answer values, and the boundary search looked among array positions.
Set the bounds of the search. The answer can't be smaller than the longest task: one task has to fit into its chunk whole. So lo = max(nums). The answer can't be bigger than the sum of all tasks, with everything in one chunk. So hi = sum(nums). Then run the boundary search from lesson 30 on the range from lo to hi. Check the middle cap. If it works, set hi = mid. If not, set lo = mid + 1. At the end, return lo.
Trace it on [7, 2, 5, 10, 8], k = 2. Bounds: lo = 10 (the longest task), hi = 32 (the sum of all tasks).
- The middle of 10 and 32 is 21. Chunks
7 + 2 + 5 = 14and10 + 8 = 18, 2 in all. It works, sohi = 21. - The middle of 10 and 21, rounded down, is 15. Chunks 14, 10 and 8, 3 in all. It doesn't work, so
lo = 16. - The middle of 16 and 21, rounded down, is 18. Chunks 14 and 18, 2 in all. It works, so
hi = 18. - The middle of 16 and 18 is 17. Chunks 14, 10 and 8, 3 in all. It doesn't work, so
lo = 18. loandhimeet at 18. The answer is 18.
4. What it costs
Time: O(n · log(range)). Binary search makes about log(range) steps, and each step runs one O(n) pass of the check. Here the log is taken of the spread of possible answers (sum - max), not of the array length. In the lesson's example the spread is 32 - 10 = 22, and the search took 4 steps. Memory: O(1) beyond the input.
You could also find the split with dynamic programming (a method that builds the answer from the answers to smaller subproblems). Writing it without mistakes is usually harder. A monotonic yes/no check plus a search over the answer is simpler, and it is harder to get wrong.
5. Where this shows up
Load balancing and choosing the size of shards (the pieces data is split into across servers): work is cut so that the busiest server stays under a limit. Planning of the kind "ship all packages within D days". Tuning rate limits. The interview problem "Koko eats bananas": find the smallest speed at which the work is done in time. Picking the smallest machine that still meets an SLA (the service level promised to a customer). git bisect has the same shape: the answer is the first bad commit, and isBad(commit) is the monotonic check, over a range of commits instead of load values.
smallestFeasible(4, 16, (cap) => canShip([3, 2, 2, 4, 1, 4], 3, cap))lo
hi
Ship packages [3, 2, 2, 4, 1, 4] in order within 3 days. The capacity is at least 4 (the heaviest package) and at most 16 (everything at once).
Bars: the package weights. Every capacity check reads all of them in order.
One operation is one package weight read. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n·S)O(n log S)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- minimize the maximum / maximize the minimum
- smallest value that satisfies a condition
- find the smallest capacity/speed/days that works
- answer lies in a numeric range, not an array position
- a feasibility check is monotonic (true after some point)
Looks similar, isn't
- Binary search (array)
There the range holds real stored data. Here it holds every value the answer might take.
- Greedy (exchange argument)
The feasibility test is often greedy itself. The search only decides which candidate to test.
- Linear search
Trying candidates one by one is correct but slow. A monotone test lets you skip half of them.
- Dynamic programming (1-D)
DP builds the answer up from smaller answers. Here the answer is guessed and then checked.
A range of 1e9 needs about 30 tests. Total cost is O(n log range) when one test costs O(n).
On LeetCode
Problems that ask for the smallest speed, capacity or limit that still works, or the largest one that is still allowed. Write a yes or no check for one guess, then binary search the range of answers.
This is the lesson task, with the same greedy feasible check.
The guess is a daily capacity, and the check counts the days needed to ship everything in order.
The guess is an eating speed, and the check adds up the hours each pile takes.
The guess is the divisor, and the check compares the sum of rounded-up quotients with threshold.
Your task (Tier 1)
Write the function minLargestSplit(nums, k).
Cut the list into k parts. Each part is a run of neighbouring numbers in their original order, and no part is empty. Every part has a sum. The largest of these sums should be as small as possible. Return that smallest possible largest sum.
- Input:
nums, a list of numbers that are each0or more, andk, how many parts to cut it into. Example:[7, 2, 5, 10, 8]withk = 2. - Return: the smallest value the largest part sum can have.
Steps:
- Write a helper
feasible(cap). Walk the list and add the numbers to the current part. If the next number would push the sum pastcap, start a new part. The limit works if you end up withkparts or fewer. - The answer lies between the biggest single number (a part can never be smaller than that) and the sum of all numbers (one part holding everything).
- Search that range with binary search. Try the middle
cap. Iffeasible(cap)givestrue, try smaller. If not, try bigger. Return the smallestcapthat works.
Done when all tests pass:
[7, 2, 5, 10, 8],k = 2->18[1, 2, 3, 4, 5],k = 2->9[1, 4, 4],k = 3->4(one number per part, so the answer is the biggest number)[1, 2, 3],k = 1->6(one part, the whole sum)[1, 2, 3],k = 3->3(one number per part)[5],k = 1->5(one number)[2, 2, 2],k = 3->2(equal parts)
Practice
minLargestSplit
minLargestSplit(nums, k) -> number
export function minLargestSplit(nums, k) {
// Your code here. The task is described in the box above the editor.
}
Running as a guest
The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.
Hint ladder
Stuck? Reveal one rung at a time, but try it yourself first.