Problem Statement
Given:
-
books[i]= pages in ith book -
mstudents
Allocate books such that:
- Every student gets at least one book.
- Books are allocated contiguously.
- Every book is assigned.
Minimize:
Maximum pages assigned to any student
Return the minimum possible value.
Brute Force Intuition
In an interview, you can explain it like this:
Try every possible maximum page limit and check whether it is possible to distribute books among students while respecting that limit.
This works but is inefficient.
Complexity
- Time Complexity: O(N × Sum)
- Space Complexity: O(1)
Moving Towards the Optimal Approach
Think about the answer.
Minimum possible answer:
Maximum book pages
because one student must take that book.
Maximum possible answer:
Sum of all pages
when one student takes all books.
So answer lies in:
[max(book), sum(book)]
This screams:
Binary Search on Answer
Pattern Recognition
Whenever you see:
- Minimize Maximum
- Maximize Minimum
- Feasibility Check
Think:
Binary Search on Answer
Key Observation
Suppose:
Maximum allowed pages = X
Can we allocate books to at most:
m students
?
If yes:
Try smaller answer
If no:
Need larger answer
Feasibility Function
For every book:
Add pages to current student
If limit exceeded:
Assign new student
Count students required.
Optimal Java Solution
class Solution {
public int findPages(int[] arr,
int n,
int m) {
if (m > n)
return -1;
int low = 0;
int high = 0;
for (int pages : arr) {
low = Math.max(low, pages);
high += pages;
}
while (low <= high) {
int mid = low + (high - low) / 2;
int students =
countStudents(arr, mid);
if (students > m) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
private int countStudents(int[] arr,
int maxPages) {
int students = 1;
int pages = 0;
for (int book : arr) {
if (pages + book <= maxPages) {
pages += book;
} else {
students++;
pages = book;
}
}
return students;
}
}
Dry Run
Input
books = [12,34,67,90]
students = 2
Search Space:
low = 90
high = 203
Iteration 1
mid = 146
Allocation:
12 + 34 + 67 = 113
Next 90 exceeds
Student 2 gets:
90
Students Needed:
2
Valid.
Try smaller answer.
Iteration 2
mid = 117
Students Needed:
2
Still valid.
Try smaller.
Eventually:
113
becomes answer.
Why Binary Search Works?
If:
113 pages works
Then:
114
115
116
...
will also work.
This monotonic behaviour allows Binary Search.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N × log(Sum)) |
| Space Complexity | O(1) |
Interview One-Liner
Binary search the maximum pages a student can receive and check if allocation is possible within m students.
Pattern Learned
Minimize Maximum
+
Feasibility Check
=> Binary Search on Answer
Similar Problems
- Allocate Minimum Pages
- Aggressive Cows
- Painter's Partition
- Capacity To Ship Packages
- Koko Eating Bananas
- Minimum Days To Make Bouquets
Memory Trick
Think:
Can all books be allocated
if no student gets
more than X pages?
YES
→ Try Smaller
NO
→ Increase X
Mental Model
Answer Exists in Range
↓
Check Feasibility
↓
Binary Search
Whenever you hear:
"Minimize the maximum"
your brain should immediately think:
Binary Search on Answer 🚀