You have a shelf of n books. The i-th book has arr[i] pages. You also have an integer k — the number of students.
Distribute all the books so that:
The busiest student is the one who receives the most pages in total. Among all valid distributions, find the one whose busiest student reads as few pages as possible — and return that number of pages.
If no valid distribution exists (more students than books), return -1.
Note: the answer always fits in a 32-bit integer.
x pages, how fast can you check whether that is achievable?x, pack greedily left to right: fill the current student until the next book would exceed x, then start a new student. This uses the fewest students possible — if that count is at most k, the budget x is feasible.max(arr) and sum(arr) — each probe is one O(n) greedy pass.max(arr) is achievable. Worse, the greedy counter assumes every single book fits within the budget — probing below max(arr) silently undercounts students and corrupts the search.k students, every allocation does.[max(arr), sum(arr)], which is monotone in feasibility — not over the array itself.x, run the greedy pass once more with budget x and record where each new student starts — those indices are the cut points of an optimal allocation.O(k · n^2) (improvable with monotonicity tricks), but for n up to 10^6 the binary-search-on-answer approach is the practical winner.Input: arr = [12, 34, 67, 90], k = 2 Output: 113 The possible splits are [12] | [34,67,90] (busiest reads 191), [12,34] | [67,90] (busiest reads 157), and [12,34,67] | [90] (busiest reads 113). The last split minimizes the busiest student's load, so the answer is 113.
Input: arr = [15, 17, 20], k = 5 Output: -1 There are 5 students but only 3 books, so someone would get no book. Allocation is impossible.
- 1 <= arr.size <= 10^6 - 1 <= arr[i] <= 10^4 - 1 <= k <= 10^4 - The answer always fits in a 32-bit integer
This is the gateway problem for one of the most powerful interview patterns: binary search on the answer. You will learn to stop hunting for the perfect arrangement directly and instead interrogate candidate answers until only one survives.
In plain English: split the array into k contiguous, non-empty pieces so that the largest piece-sum is as small as possible, and return that sum. If k > n, no split exists — return -1.
Worked example — arr = [12, 34, 67, 90], k = 2
books: 12 34 67 90 k = 2 students try every place to cut the shelf: [12] [34, 67, 90] → busiest reads 191 [12, 34] [67, 90] → busiest reads 157 [12, 34, 67] [90] → busiest reads 113 ✓ answer: 113
Two or three sharp questions before coding show the interviewer you think in contracts, not guesses.
“Must each student receive a contiguous block of books from the shelf?”
Yes — this is what turns the task into an array-partition problem instead of a general assignment problem, and it is exactly why a greedy left-to-right check will work.
“Must every book be allocated, with no book shared?”
Yes. All books are handed out and each book goes to exactly one student, so the k chunks tile the whole array.
“What if there are more students than books?”
Each student needs at least one book, so k greater than n is impossible — return -1.
“What happens when k is 1, or k equals n?”
With k = 1 one student reads everything, so the answer is sum(arr); with k = n each student gets one book, so the answer is max(arr). These are free sanity anchors for the search range.
“How large can n and the page counts get?”
n reaches 10^6 with values up to 10^4 — an O(n^2) partition DP is too slow, but a linear feasibility check repeated O(log) times fits easily. The total page count can reach 10^10, so use 64-bit intermediates in fixed-width languages.
Before I code, let me confirm the allocation rules.
Each student gets a contiguous block of the shelf, every book is allocated, and no book is shared — correct?
If there are more students than books, I will return -1.
Since n can reach a million, I am aiming for binary search on the answer with a greedy linear feasibility check.
Someone must take the thickest book, so no valid answer can be below max(arr). And the worst case — one student takes everything — costs exactly sum(arr). Every candidate answer lives in the range [max(arr), sum(arr)].
Call a page budget x feasible if the shelf can be split so no student exceeds x while using at most k students. If x is feasible, any larger budget is trivially feasible too (the same cuts still work). So the answer space looks like a staircase:
budget: 90 99 105 112 | 113 120 157 191
feasible? no no no no | yes yes yes yes
^ first yes = the answerThe answer is the first yes — and finding the first yes in a monotone sequence is exactly what binary search does.
Walk the shelf left to right, handing books to the current student until the next book would push them past x; then seal their pile and move to the next student. Stuffing each student as full as possible never wastes a cut, so this greedy uses the fewest students possible for budget x — one O(n) pass tells you feasible or not.
| Brute force | Binary search on answer | |
|---|---|---|
| Time | O(n · (S − M)) | O(n log(S − M)) |
| Space | O(1) | O(1) |
Here S = sum(arr) and M = max(arr). The full code for both approaches is in the Approaches selector below.
Key takeaway
When you cannot construct the optimal arrangement directly but you can check a guessed answer in linear time — and feasibility is monotone — binary search the answer space. The smallest feasible guess is the optimum.
if k > n: return -1
lo = max(arr), hi = sum(arr)
while lo < hi:
mid = (lo + hi) / 2
if studentsNeeded(mid) <= k: hi = mid # feasible → try smaller
else: lo = mid + 1 # too stingy → raise it
return lo