Loading…

mediumBinary SearchFrequently asked

Allocate Minimum Number of Pages

Binary Search · 11 of 16 · 11 min

You are given an array books of n integers where books[i] is the number of pages in the i-th book, and an integer k — the number of students.

Allocate all the books to the students such that:

Each student gets at least one book.
Each student is assigned a contiguous block of books.
Every book is assigned to exactly one student.

Among all valid allocations, minimize the maximum number of pages assigned to any single student, and return that minimum value. If allocation is impossible (k > n), return -1.

In plain English

Cut the book array into k contiguous blocks. Each block's cost is the sum of its pages; the allocation's cost is the largest block sum. You want the cut that makes that largest block as small as possible. The output is one number — the minimized maximum — which is the tell for binary search on the answer.

Examples

Example 1

Input: books = [12, 34, 67, 90], k = 2
Output: 113
Note: Best cut is [12, 34, 67] | [90] → block sums 113 and 90 → maximum 113. Every other cut has a larger maximum (e.g. [12,34]|[67,90] gives 157).

Example 2

Input: books = [10, 20, 30, 40], k = 2
Output: 60
Note: Cut [10, 20, 30] | [40] → 60 and 40 → max 60. Cut [10,20]|[30,40] → 30 and 70 → max 70. Minimum maximum is 60.

Example 3

Input: books = [15, 17, 20], k = 5
Output: -1
Note: Five students but only three books — at least two students would get nothing, so no valid allocation exists.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ k ≤ 10⁵
1 ≤ books[i] ≤ 10⁴
Return -1 when k > n

Clarifying questions4First question: Must each student's books be contiguous?Explore questions

Q1.Must each student's books be contiguous?
Yes. Student blocks are consecutive in the array. That's what lets a single left-to-right greedy pass count the students a cap forces.
Q2.What if there are more students than books?
Impossible — some student would get zero books, violating 'at least one book each'. Return -1 immediately.
Q3.Can the array be reordered?
No. The order is fixed; you only choose where to cut. Sorting would change which blocks are contiguous.
Q4.Why is the smallest possible answer max(books)?
Whichever student holds the largest single book carries at least that many pages, so no allocation can push the maximum below max(books).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Binary-search the answer — the maximum pages any single student carries. For a candidate cap x, greedily walk the books left to right, opening a new student whenever the running sum would exceed x, and count students. 'Can we finish within k students if nobody exceeds x pages?' is monotonic in x, so binary search finds the smallest feasible x in O(n log(sum)). The lower bound is max(book), the upper bound is sum(books).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you see that the answer (the max-pages value) is the search space, can pin the bounds at [max(books), sum(books)], and can argue the feasibility predicate is monotone before coding the binary search.

Where candidates slip

Setting lo = 0 instead of max(books), forgetting the k > n impossibility guard, or going the wrong direction on a feasible mid (right instead of left) because the min/max direction got flipped.

How to stand out

State 'feasible(x) is monotone increasing, I want the smallest true', justify lo = max(books) out loud, and note the O(n) greedy count is exact because the split is contiguous and books are non-negative.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan Over the Answer — Baseline	`O(n · sum)`	`O(1)`	Open with this to show you've identified the search space (the page cap) and the feasibility check. Then note the scan range is sum(books), which is too large.	Read
2	Binary Search on the Page Cap (Optimal)Optimal	`O(n log(sum))`	`O(1)`	The intended answer. Frame it as 'feasible(cap) is monotone, so binary-search the smallest feasible cap'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMinimize the MAX pages per studentk > n ?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan Over the Answer — Baseline

TimeO(n · sum)SpaceO(1)

Open with this to show you've identified the search space (the page cap) and the feasibility check. Then note the scan range is sum(books), which is too large.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is some page cap between max(books) and sum(books). What if you tried every cap from max(books) upward and returned the first that works?

2Hint 2Explore hint

For a fixed cap x, can you count how many students you'd need? Walk the books, keep a running block sum, and start a new student whenever adding the next book would exceed x.

3Hint 3Explore hint

The first cap whose student-count is ≤ k is the answer — once a cap works, every larger cap works too. But sum(books) can be ~10⁹, so the scan is the bottleneck.

A · Core idea

First nail the reframing: you are not choosing books, you are choosing a number — the page cap that the busiest student is allowed to reach. That number lives in [max(books), sum(books)]. The lower end is max(books) because the student holding the biggest book already carries that many pages; the upper end is sum(books) because one student could carry every book.

The feasibility check counts students. Fix a cap x. Sweep the books left to right with a running block sum. Add the current book to the running sum; if that would exceed x, close the current student's block and open a new student starting with this book. The number of students opened is exactly the minimum needed under cap x — because the split is contiguous and pages are non-negative, packing each student as full as legally possible minimizes how many students you use.

Why greedy-fill is exact, not approximate. With contiguous blocks and non-negative pages, the running sum only grows within a block. Delaying a cut (keeping a student busier) never forces more students later; it can only ever help. So 'fill each student to the cap, then cut' produces the fewest students for that cap — a precise yes/no feasibility answer.

Why we walk caps from low to high. The first cap whose student count is ≤ k is the minimum feasible cap, which is exactly the answer. And we can be sure it's safe to stop there: raising the cap only lets each student absorb more, so it never increases the student count. That 'larger cap ⇒ never worse' fact is the monotonicity we'll exploit.

Why we don't ship this. sum(books) can be on the order of 10⁵ · 10⁴ = 10⁹. Running an O(n) check up to a billion times blows the time limit. Since feasibility is monotone in the cap, binary-search the boundary instead of scanning to it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

books = [12, 34, 67, 90], k = 2

Array state

student 1

12 → 46 → 113 (all ≤ 113)

[0]

[1]

fill ↓

[2]

[3]

Current pointerResolved stateNot processed

Final result113

C · Code with teaching comments

Reference implementation previewpublic int findPages(int[] books, int k) { if (k > books.length) return -1; int lo = 0, hi = 0; for (int b : books) { lo = Math.max(lo, b); hi += b; } for (int x = lo; x <= hi; x++) {Explore the full code

solution.javaJava

Linear Scan Over the Answer — Baseline — reference

4 teaching notes

1
public int findPages(int[] books, int k) {
2
    // More students than books → someone gets zero → impossible.
3
    if (k > books.length) return -1;
4
    int lo = 0, hi = 0;
5
    // Answer bounds: lo = max(book) (one student must carry the biggest), hi = total
6
    // pages.
7
    for (int b : books) { lo = Math.max(lo, b); hi += b; }
8
    for (int x = lo; x <= hi; x++) {
9
        // First cap that fits within k students is the minimized maximum.
10
        if (studentsNeeded(books, x) <= k) {
11
            return x;          // first feasible cap is the minimum
12
        }
13
    }
14
    return hi;
15
}
16
 
17
private int studentsNeeded(int[] books, int maxPages) {
18
    int students = 1, pages = 0;
19
    for (int b : books) {
20
        // Adding this book would overflow the cap → start a fresh student.
21
        if (pages + b > maxPages) {
22
            students++;        // open a new student starting with this book
23
            pages = b;
24
        } else {
25
            pages += b;
26
        }
27
    }
28
    return students;
29
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.29 lines

D · Why it works and complexityO(n · sum) timeO(1) spaceOpen the invariant and proofExplore the proof

The observation 'a larger cap never needs more students' is the proof that feasible(x) is monotone increasing. That single fact is the license to swap the linear scan for a binary search — the only change is how you move through the candidate caps.

ComplexityO(n · sum) time, O(1) space — Each candidate cap (up to sum(books)) triggers an O(n) greedy student count. That's O(n · sum) — acceptable only when the total page count is tiny, far too slow under the real constraints.

E · Edge cases and pitfalls3Starting the scan at 0 instead of max(books) — wastes time on impossible caps.Explore edge cases

Pitfalls

Starting the scan at 0 instead of max(books) — wastes time on impossible caps.
Letting x run to sum(books) ≈ 10⁹ — the scan times out.
Forgetting the k > n guard — the count logic returns nonsense instead of -1.

03.2

Approach 2 of 2 · Optimal

Binary Search on the Page Cap (Optimal)

TimeO(n log(sum))SpaceO(1)

The intended answer. Frame it as 'feasible(cap) is monotone, so binary-search the smallest feasible cap'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You showed feasible(cap) is false for small caps and true for large caps, flipping exactly once. What finds that flip in logarithmic time?

2Hint 2Explore hint

Binary-search the cap in [max(books), sum(books)]. At each mid, run the O(n) greedy student count. If it needs ≤ k students, mid is feasible — record it and try smaller; otherwise try larger.

3Hint 3Explore hint

Because you MINIMIZE, on a feasible mid record ans = mid and move hi = mid - 1; on infeasible move lo = mid + 1. The last feasible mid is the answer.

A · Core idea

Binary search on the answer applies whenever the answer is a number with a monotone feasibility predicate. Here both conditions hold cleanly.

The monotonic predicate, precisely. Define feasible(x) = true if the books can be split into at most k contiguous blocks each summing to ≤ x. We argued in the baseline that raising the cap never increases the number of students forced — a roomier cap only lets each student absorb more books. So as x rises from max(books) to sum(books), feasible(x) goes [F, F, …, F, T, T, …, T]: false while the cap is too tight, true once it's loose enough, flipping exactly once. The answer is the smallest `x` that is true — the left boundary of the true region.

The feasibility check is the same greedy count. studentsNeeded(x) sweeps the books once, accumulating a block sum and opening a new student whenever the next book would push the block past x. Because the split is contiguous and pages are non-negative, filling each student to the cap before cutting yields the minimum student count for that cap — an exact predicate, which is the non-negotiable requirement for binary-search-on-the-answer.

Driving toward the smallest true. Set lo = max(books), hi = sum(books). Compute mid = lo + (hi − lo) / 2. If studentsNeeded(mid) ≤ k, then mid is achievable, but a tighter cap might also work — so record ans = mid and search the lower half with hi = mid − 1. If mid needs more than k students, it's too tight — search upward with lo = mid + 1. When lo > hi, ans holds the smallest feasible cap.

The off-by-one traps, named. (1) lo = 0 instead of max(books) doesn't break correctness but lets binary search waste iterations on caps that can't even hold the biggest book — and worse, if you forget to clamp, an infeasible-everywhere range can mislead. (2) Updating ans on the infeasible branch returns a cap that doesn't actually fit k students. (3) Mixing up the direction — this is minimize the maximum, so a feasible mid means 'try smaller', i.e. move hi left. Going right there returns a cap that's larger than necessary. Recite the invariant — 'ans is always a cap that fits within k students' — and the pointer moves fall out correctly.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

books = [12, 34, 67, 90], k = 2

Array state

lo=90, hi=203

mid=146 feasible(T) → ans=146, hi=145

lo ↓

[0]

...

[1]

113

[2]

...

[3]

mid ↓

146

[4]

...

[5]

hi ↓

203

[6]

Current pointerResolved stateNot processed

Final result113

C · Code with teaching comments

solution.javaJava

Binary Search on the Page Cap (Optimal) — optimal

6 teaching notes

1
public int findPages(int[] books, int k) {
2
    // Impossibility guard before computing any bounds.
3
    if (k > books.length) return -1;
4
    int lo = 0, hi = 0;
5
    // lo = max(book) is the tight lower bound; hi = sum is one-student-takes-all.
6
    for (int b : books) { lo = Math.max(lo, b); hi += b; }
7
    int ans = hi;
8
    while (lo <= hi) {
9
        // Overflow-safe midpoint — sum can reach ~10⁹ which is near int's limit.
10
        int mid = lo + (hi - lo) / 2;
11
        if (studentsNeeded(books, mid) <= k) {
12
            ans = mid;        // feasible → remember it, try a SMALLER cap
13
            // Feasible → MINIMIZE, so search for an even smaller cap on the left.
14
            hi = mid - 1;
15
        } else {
16
            lo = mid + 1;     // infeasible → allow a BIGGER cap
17
        }
18
    }
19
    return ans;
20
}
21
 
22
private int studentsNeeded(int[] books, int maxPages) {
23
    int students = 1, pages = 0;
24
    for (int b : books) {
25
        if (pages + b > maxPages) {
26
            students++;
27
            pages = b;
28
        } else {
29
            pages += b;
30
        }
31
    }
32
    return students;
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n log(sum)) timeO(1) spaceOpen the invariant and proofExplore the proof

Notice this is the mirror image of Aggressive Cows: there feasible was monotone decreasing and we maximized (feasible ⇒ go right); here feasible is monotone increasing and we minimize (feasible ⇒ go left). Same skeleton, opposite direction. Internalize 'which side is true, and am I taking the first or last true' and every binary-search-on-the-answer variant becomes mechanical.

ComplexityO(n log(sum)) time, O(1) space — The cap range spans sum(books), so binary search runs O(log(sum)) iterations, each doing the O(n) greedy count. Total O(n log(sum)). Computing lo and hi is O(n); space is O(1).

E · Edge cases and pitfalls7books = [50], k = 1 — lo = hi = 50; the single student carries all 50 pages → answer 50.Explore edge cases

Edge cases handled

books = [50], k = 1lo = hi = 50; the single student carries all 50 pages → answer 50.
books = [7, 7, 7, 7], k = 4One book each → max block is 7. lo = 7 is already feasible, so the answer is 7.
books = [10, 20], k = 5k > n → returns -1 via the guard before binary search.

Pitfalls

Setting lo = 0 instead of max(books) — searches caps that can't hold the biggest book.
Recording ans on the infeasible branch — returns a cap that needs more than k students.
Going right on a feasible mid — that maximizes instead of minimizing.
Using (lo + hi) / 2 — overflows when sum approaches the int limit.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int findPages(int[] books, int k) { if (k > books.length) return -1; int lo = 0, hi = 0; for (int b : books) { lo = Math.max(lo, b); hi += b; } int ans = hi;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong lower bound

The busiest student must carry at least the largest single book. Starting lo at 0 explores caps that can never be feasible and risks an off-by-one when seeding ans.

Explore the code comparison

Don't write this

int lo = 0, hi = 0;
for (int b : books) hi += b;   // lo never raised to max(book)

Write this instead

int lo = 0, hi = 0;
for (int b : books) { lo = Math.max(lo, b); hi += b; }

Missing the impossibility guard

With k > n some student gets zero books. Without the guard, studentsNeeded never exceeds n and you return a bogus cap instead of -1.

Explore the code comparison

Don't write this

def find_pages(self, books, k):
    lo, hi = max(books), sum(books)
    # no k > len(books) check
    ...

Write this instead

def find_pages(self, books, k):
    if k > len(books):
        return -1
    lo, hi = max(books), sum(books)
    ...

Wrong direction on a feasible mid

This problem minimizes the maximum, so a feasible cap means 'a smaller cap might also work'. Moving lo right here returns a cap larger than the true minimum.

Explore the code comparison

Don't write this

if (studentsNeeded(books, mid) <= k) {
    lo = mid + 1;          // WRONG: walks away from smaller feasible caps
}

Write this instead

if (studentsNeeded(books, mid) <= k) {
    ans = mid;
    hi = mid - 1;          // minimize → search for an even smaller cap
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search on the answer + greedy partition-count feasibility

Code pattern to memorize

if k > n: return -1            # more students than books → impossible
lo, hi = max(books), sum(books)
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if canAllocate(mid):       # students needed with cap mid <= k ?
        ans = mid; hi = mid - 1    # feasible → try a SMALLER cap
    else:
        lo = mid + 1               # infeasible → allow a BIGGER cap

Rules to remember

1Books are assigned contiguously — student i gets a prefix-block of consecutive books. That contiguity is what makes the greedy count a single left-to-right sweep.
2Lower bound is max(books), not 0: one student must carry the single largest book, so the answer can never be below it. Upper bound is sum(books): one student carrying everything.
3The predicate is monotone increasing: if cap x works (needs ≤ k students), every cap > x works too. We MINIMIZE, so on a feasible mid go left (hi = mid − 1) and record it.
4Guard k > n up front → return −1. With more students than books, someone gets zero books and the allocation is undefined.
5Feasibility counts the students forced by the cap: start a fresh student whenever adding the next book would exceed the cap, then compare the count to k. Bail early once the count passes k.

Use this pattern when

Split a contiguous sequence into k groups and optimize the worst (largest) group sum
The objective is MINIMIZE the maximum (or maximize the minimum) of group sums
You can count, in O(n), how many groups a given cap forces
The answer is a number in [max(element), sum(elements)]

Choose another pattern when

Groups need not be contiguous → this becomes a partition/DP problem, not binary search on the answer
You must output the actual partition, not just its cost → still binary search, but reconstruct after
Element values can be negative → prefix sums aren't monotone and the greedy count breaks
k can exceed n and that's allowed with empty groups → redefine feasibility carefully

Interview takeaway

Allocate Pages is the canonical 'minimize the largest group' problem. Spot the contiguous-split + min-max signature and you instantly know the move: bound the answer by [max, sum], binary-search it, and check feasibility with a one-pass greedy group count. Painter's Partition and Split Array Largest Sum are the exact same algorithm with relabelled words.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Binary Search on the Answer (minimize the maximum). Trigger on 'split a contiguous sequence into k groups and minimize the largest group sum'. Bounds are [max(element), sum(elements)]; feasibility is an O(n) greedy group count. Identical to Painter's Partition and Split Array Largest Sum.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Painter's Partition
Identical algorithm — k painters, board lengths, minimize total paint time.
Split Array Largest Sum
Coming soon
Same problem on LeetCode: split into k subarrays minimizing the largest subarray sum.
Aggressive Cows
The mirror image — maximize the minimum gap; feasible is monotone the other way.
Koko Eating Bananas
Binary-search the eating speed; feasible(speed) = finishes within h hours.

Same pattern

←

Aggressive Cows

Continue · Next problem

Kth Smallest Element in an Array

mediumBinary SearchFrequently asked

Allocate Minimum Number of Pages

Binary Search · 11 of 16 · 11 min

You are given an array books of n integers where books[i] is the number of pages in the i-th book, and an integer k — the number of students.

Allocate all the books to the students such that:

Each student gets at least one book.
Each student is assigned a contiguous block of books.
Every book is assigned to exactly one student.

Among all valid allocations, minimize the maximum number of pages assigned to any single student, and return that minimum value. If allocation is impossible (k > n), return -1.

In plain English

Examples

Example 1

Input: books = [12, 34, 67, 90], k = 2
Output: 113
Note: Best cut is [12, 34, 67] | [90] → block sums 113 and 90 → maximum 113. Every other cut has a larger maximum (e.g. [12,34]|[67,90] gives 157).

Example 2

Input: books = [10, 20, 30, 40], k = 2
Output: 60
Note: Cut [10, 20, 30] | [40] → 60 and 40 → max 60. Cut [10,20]|[30,40] → 30 and 70 → max 70. Minimum maximum is 60.

Example 3

Input: books = [15, 17, 20], k = 5
Output: -1
Note: Five students but only three books — at least two students would get nothing, so no valid allocation exists.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ k ≤ 10⁵
1 ≤ books[i] ≤ 10⁴
Return -1 when k > n

Clarifying questions4First question: Must each student's books be contiguous?Explore questions

Q1.Must each student's books be contiguous?
Yes. Student blocks are consecutive in the array. That's what lets a single left-to-right greedy pass count the students a cap forces.
Q2.What if there are more students than books?
Impossible — some student would get zero books, violating 'at least one book each'. Return -1 immediately.
Q3.Can the array be reordered?
No. The order is fixed; you only choose where to cut. Sorting would change which blocks are contiguous.
Q4.Why is the smallest possible answer max(books)?
Whichever student holds the largest single book carries at least that many pages, so no allocation can push the maximum below max(books).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Setting lo = 0 instead of max(books), forgetting the k > n impossibility guard, or going the wrong direction on a feasible mid (right instead of left) because the min/max direction got flipped.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan Over the Answer — Baseline	`O(n · sum)`	`O(1)`	Open with this to show you've identified the search space (the page cap) and the feasibility check. Then note the scan range is sum(books), which is too large.	Read
2	Binary Search on the Page Cap (Optimal)Optimal	`O(n log(sum))`	`O(1)`	The intended answer. Frame it as 'feasible(cap) is monotone, so binary-search the smallest feasible cap'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan Over the Answer — Baseline

TimeO(n · sum)SpaceO(1)

Open with this to show you've identified the search space (the page cap) and the feasibility check. Then note the scan range is sum(books), which is too large.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is some page cap between max(books) and sum(books). What if you tried every cap from max(books) upward and returned the first that works?

2Hint 2Explore hint

For a fixed cap x, can you count how many students you'd need? Walk the books, keep a running block sum, and start a new student whenever adding the next book would exceed x.

3Hint 3Explore hint

The first cap whose student-count is ≤ k is the answer — once a cap works, every larger cap works too. But sum(books) can be ~10⁹, so the scan is the bottleneck.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

books = [12, 34, 67, 90], k = 2

Array state

student 1

12 → 46 → 113 (all ≤ 113)

[0]

[1]

fill ↓

[2]

[3]

Current pointerResolved stateNot processed

Final result113

C · Code with teaching comments

solution.javaJava

Linear Scan Over the Answer — Baseline — reference

4 teaching notes

1
public int findPages(int[] books, int k) {
2
    // More students than books → someone gets zero → impossible.
3
    if (k > books.length) return -1;
4
    int lo = 0, hi = 0;
5
    // Answer bounds: lo = max(book) (one student must carry the biggest), hi = total
6
    // pages.
7
    for (int b : books) { lo = Math.max(lo, b); hi += b; }
8
    for (int x = lo; x <= hi; x++) {
9
        // First cap that fits within k students is the minimized maximum.
10
        if (studentsNeeded(books, x) <= k) {
11
            return x;          // first feasible cap is the minimum
12
        }
13
    }
14
    return hi;
15
}
16
 
17
private int studentsNeeded(int[] books, int maxPages) {
18
    int students = 1, pages = 0;
19
    for (int b : books) {
20
        // Adding this book would overflow the cap → start a fresh student.
21
        if (pages + b > maxPages) {
22
            students++;        // open a new student starting with this book
23
            pages = b;
24
        } else {
25
            pages += b;
26
        }
27
    }
28
    return students;
29
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.29 lines

D · Why it works and complexityO(n · sum) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Starting the scan at 0 instead of max(books) — wastes time on impossible caps.Explore edge cases

Pitfalls

Starting the scan at 0 instead of max(books) — wastes time on impossible caps.
Letting x run to sum(books) ≈ 10⁹ — the scan times out.
Forgetting the k > n guard — the count logic returns nonsense instead of -1.

03.2

Approach 2 of 2 · Optimal

Binary Search on the Page Cap (Optimal)

TimeO(n log(sum))SpaceO(1)

The intended answer. Frame it as 'feasible(cap) is monotone, so binary-search the smallest feasible cap'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You showed feasible(cap) is false for small caps and true for large caps, flipping exactly once. What finds that flip in logarithmic time?

2Hint 2Explore hint

Binary-search the cap in [max(books), sum(books)]. At each mid, run the O(n) greedy student count. If it needs ≤ k students, mid is feasible — record it and try smaller; otherwise try larger.

3Hint 3Explore hint

Because you MINIMIZE, on a feasible mid record ans = mid and move hi = mid - 1; on infeasible move lo = mid + 1. The last feasible mid is the answer.

A · Core idea

Binary search on the answer applies whenever the answer is a number with a monotone feasibility predicate. Here both conditions hold cleanly.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

books = [12, 34, 67, 90], k = 2

Array state

lo=90, hi=203

mid=146 feasible(T) → ans=146, hi=145

lo ↓

[0]

...

[1]

113

[2]

...

[3]

mid ↓

146

[4]

...

[5]

hi ↓

203

[6]

Current pointerResolved stateNot processed

Final result113

C · Code with teaching comments

solution.javaJava

Binary Search on the Page Cap (Optimal) — optimal

6 teaching notes

1
public int findPages(int[] books, int k) {
2
    // Impossibility guard before computing any bounds.
3
    if (k > books.length) return -1;
4
    int lo = 0, hi = 0;
5
    // lo = max(book) is the tight lower bound; hi = sum is one-student-takes-all.
6
    for (int b : books) { lo = Math.max(lo, b); hi += b; }
7
    int ans = hi;
8
    while (lo <= hi) {
9
        // Overflow-safe midpoint — sum can reach ~10⁹ which is near int's limit.
10
        int mid = lo + (hi - lo) / 2;
11
        if (studentsNeeded(books, mid) <= k) {
12
            ans = mid;        // feasible → remember it, try a SMALLER cap
13
            // Feasible → MINIMIZE, so search for an even smaller cap on the left.
14
            hi = mid - 1;
15
        } else {
16
            lo = mid + 1;     // infeasible → allow a BIGGER cap
17
        }
18
    }
19
    return ans;
20
}
21
 
22
private int studentsNeeded(int[] books, int maxPages) {
23
    int students = 1, pages = 0;
24
    for (int b : books) {
25
        if (pages + b > maxPages) {
26
            students++;
27
            pages = b;
28
        } else {
29
            pages += b;
30
        }
31
    }
32
    return students;
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n log(sum)) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7books = [50], k = 1 — lo = hi = 50; the single student carries all 50 pages → answer 50.Explore edge cases

Edge cases handled

books = [50], k = 1lo = hi = 50; the single student carries all 50 pages → answer 50.
books = [7, 7, 7, 7], k = 4One book each → max block is 7. lo = 7 is already feasible, so the answer is 7.
books = [10, 20], k = 5k > n → returns -1 via the guard before binary search.

Pitfalls

Setting lo = 0 instead of max(books) — searches caps that can't hold the biggest book.
Recording ans on the infeasible branch — returns a cap that needs more than k students.
Going right on a feasible mid — that maximizes instead of minimizing.
Using (lo + hi) / 2 — overflows when sum approaches the int limit.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong lower bound

The busiest student must carry at least the largest single book. Starting lo at 0 explores caps that can never be feasible and risks an off-by-one when seeding ans.

Explore the code comparison

Don't write this

int lo = 0, hi = 0;
for (int b : books) hi += b;   // lo never raised to max(book)

Write this instead

int lo = 0, hi = 0;
for (int b : books) { lo = Math.max(lo, b); hi += b; }

Missing the impossibility guard

With k > n some student gets zero books. Without the guard, studentsNeeded never exceeds n and you return a bogus cap instead of -1.

Explore the code comparison

Don't write this

def find_pages(self, books, k):
    lo, hi = max(books), sum(books)
    # no k > len(books) check
    ...

Write this instead

def find_pages(self, books, k):
    if k > len(books):
        return -1
    lo, hi = max(books), sum(books)
    ...

Wrong direction on a feasible mid

This problem minimizes the maximum, so a feasible cap means 'a smaller cap might also work'. Moving lo right here returns a cap larger than the true minimum.

Explore the code comparison

Don't write this

if (studentsNeeded(books, mid) <= k) {
    lo = mid + 1;          // WRONG: walks away from smaller feasible caps
}

Write this instead

if (studentsNeeded(books, mid) <= k) {
    ans = mid;
    hi = mid - 1;          // minimize → search for an even smaller cap
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search on the answer + greedy partition-count feasibility

Code pattern to memorize

if k > n: return -1            # more students than books → impossible
lo, hi = max(books), sum(books)
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if canAllocate(mid):       # students needed with cap mid <= k ?
        ans = mid; hi = mid - 1    # feasible → try a SMALLER cap
    else:
        lo = mid + 1               # infeasible → allow a BIGGER cap

Rules to remember

1Books are assigned contiguously — student i gets a prefix-block of consecutive books. That contiguity is what makes the greedy count a single left-to-right sweep.
2Lower bound is max(books), not 0: one student must carry the single largest book, so the answer can never be below it. Upper bound is sum(books): one student carrying everything.
3The predicate is monotone increasing: if cap x works (needs ≤ k students), every cap > x works too. We MINIMIZE, so on a feasible mid go left (hi = mid − 1) and record it.
4Guard k > n up front → return −1. With more students than books, someone gets zero books and the allocation is undefined.
5Feasibility counts the students forced by the cap: start a fresh student whenever adding the next book would exceed the cap, then compare the count to k. Bail early once the count passes k.

Use this pattern when

Split a contiguous sequence into k groups and optimize the worst (largest) group sum
The objective is MINIMIZE the maximum (or maximize the minimum) of group sums
You can count, in O(n), how many groups a given cap forces
The answer is a number in [max(element), sum(elements)]

Choose another pattern when

Groups need not be contiguous → this becomes a partition/DP problem, not binary search on the answer
You must output the actual partition, not just its cost → still binary search, but reconstruct after
Element values can be negative → prefix sums aren't monotone and the greedy count breaks
k can exceed n and that's allowed with empty groups → redefine feasibility carefully

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Painter's Partition
Identical algorithm — k painters, board lengths, minimize total paint time.
Split Array Largest Sum
Coming soon
Same problem on LeetCode: split into k subarrays minimizing the largest subarray sum.
Aggressive Cows
The mirror image — maximize the minimum gap; feasible is monotone the other way.
Koko Eating Bananas
Binary-search the eating speed; feasible(speed) = finishes within h hours.

Same pattern

←

Aggressive Cows

Continue · Next problem

Kth Smallest Element in an Array