Allocate Minimum Pages
Allocate Minimum Pages: split an array of book page-counts among k students, contiguous books each, minimizing the maximum pages any student reads.
- 1 <= n <= 10⁵
- 1 <= k <= n
- 1 <= pages[i] <= 10⁴
- Each student gets a contiguous block; return -1 if k > n
Intuition
Allocate minimum pages hands you an array of book page-counts and k students. Books must be given out in contiguous blocks, and the goal is to minimise the maximum pages any single student has to read.
Searching over the possible splits directly is hopeless — the number of ways to divide the array grows combinatorially. The way in is to invert the question. Instead of asking for the best split, ask a yes/no question about a candidate answer:
- Given a page cap X, can the books be divided so that no student exceeds it?
That is easy to answer greedily. Sweep the books in order, adding each to the current student until one more would break the cap, then start a new student. Greedy is optimal here because packing as much as possible into each student never increases the number of students needed. If the count comes out at or below k, the cap works.
And feasibility is monotone: if a cap of X works, so does any larger cap, since the same split still satisfies a looser limit. That means the yes/no answers form a single boundary — false below some threshold, true at and above it — which is exactly what binary search needs.
So binary search the cap between max(books) (no student can read less than the biggest single book) and sum(books) (one student reads everything). The smallest feasible cap is the answer. The same pattern solves Split Array Largest Sum and Capacity to Ship Packages Within D Days.
The mirror of aggressive cows: minimise the maximum load. Guess a page limit, greedily fill students until one overflows, and count how many you needed — fewer students needed means the limit was generous. The search bounds encode the extremes: no student can carry less than the biggest single book, and one student could carry them all.
Approach
Before reading on: price up what the direct approach costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(n log S) time and O(1) space.
Invert the problem into a yes/no test
Rather than constructing the optimal split, ask whether a given cap X is achievable. The check is far easier than the construction, and that asymmetry is what the whole technique exploits.
Write the feasibility check greedily
Sweep the books in order, accumulating pages for the current student. When adding the next book would exceed X, close that student and start a new one. Greedy is provably optimal — leaving room in a student's allocation can only require more students later.
Set the search bounds correctly
The lower bound is max(books): no cap below the largest single book can ever work, since books cannot be split. The upper bound is sum(books), where one student reads everything. Starting the search at 0 or 1 wastes iterations and can produce an off-by-one at the boundary.
Recognise the monotonicity
If cap X is feasible then every larger cap is too, because the same allocation satisfies a weaker constraint. Feasibility is therefore false-then-true across the range, which is the precondition binary search requires.
Converge on the smallest feasible cap
When mid is feasible, record it and search lower with hi = mid. When it is not, search higher with lo = mid + 1. The loop ends with lo at the minimum workable cap.
Cost of the search
Each of the O(log(sum)) binary search steps runs an O(n) feasibility sweep, giving O(n log(sum of pages)) time and O(1) space. Note the search space is the range of page totals, not the array length — the log factor is over values, not indices.
Solution & live demo
Common pitfalls
Starting the search at zero or one
lo, hi = 1, sum(books)
lo, hi = max(books), sum(books)
A limit below the largest single book is infeasible — that book fits nowhere, and the greedy check would loop or miscount. The largest book is a hard floor on any valid answer.
Missing the impossible case
def allocate_pages(books, k):
lo, hi = max(books), sum(books)if k > len(books): return -1
With more students than books, someone must get zero books, which the problem forbids — the expected answer is -1. The binary search itself would happily return a number.
Inverting the feasibility comparison
if students_needed(mid) <= k: lo = mid + 1 else: hi = mid
if students_needed(mid) <= k: hi = mid else: lo = mid + 1
Needing at most k students means the limit is workable, and since we're minimising, a workable limit becomes the new upper bound. Pushing lo up instead walks away from the answer and returns the largest infeasible value.
Edge cases
Classic GFG version returns −1; every student needs a book.
Only the full sum works — the search converges to it.