The “Allocate Minimum Pages” problem is a classic binary search question that is often asked in coding interviews.
It teaches you how to optimize allocation problems using binary search. In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.
Here’s the [Problem Link] to begin with.
Problem Statement
You are given an array arr where each element represents the number of pages in a book. There are k students, and the books are arranged in a line.
Your task is to allocate books to students such that:
- Each student gets at least one book.
- Each book is allocated to exactly one student.
- Books are allocated in a contiguous manner (no skipping).
- The goal is to minimize the maximum number of pages assigned to any student.
If it is not possible to allocate, return -1.
Input: arr[] = [12, 34, 67, 90], k = 2 Output: 113 Explanation: Allocation can be done in following ways: [12] and [34, 67, 90] Maximum Pages = 191 [12, 34] and [67, 90] Maximum Pages = 157 [12, 34, 67] and [90] Maximum Pages = 113. Therefore, the minimum of these cases is 113, which is selected as the output.
Input: arr[] = [15, 17, 20], k = 5
Output: -1
Explanation: Allocation can not be done.
Constraints:
1 <= arr.size() <= 106
1 <= arr[i] <= 103
1 <= k <= 103
Brute Force Solution (Try Every Possible Maximum)
Intuition and Approach
Let’s solve the problem in the most straightforward way:
- Try Every Maximum Pages:
Try every possible maximum pages value from the largest single book to the sum of all pages. - Check If Allocation Is Possible:
For each value, check if it is possible to allocate books so that no student gets more than that many pages. - Return the First Valid Maximum:
The first value for which allocation is possible is our answer. - Why does this work?
We check every possible value, so we’re sure to find the minimum one that works.
This approach is easy to understand but not efficient for large inputs.
Code Implementation
class Solution:
def countStudents(self, nums, pages):
n = len(nums)
students = 1
pagesStudent = 0
for i in range(n):
if pagesStudent + nums[i] <= pages:
# Add pages to current student
pagesStudent += nums[i]
else:
# Add pages to next student
students += 1
pagesStudent = nums[i]
return students
def findPages(self, arr, k) -> int:
n = len(arr)
# Book allocation impossible
if k > n:
return -1
# Calculate the range
low = max(arr)
high = sum(arr)
# Linear search for minimum maximum pages
for pages in range(low, high + 1):
if self.countStudents(arr, pages) == k:
return pages
return lowCode Explanation
- For each possible maximum pages from the largest book to the total pages, check if you can allocate books to exactly
kstudents. - The helper function
countStudentssimulates the allocation process. - Return the smallest maximum pages for which allocation is possible.
Dry Run
Input:arr = , k = 2
- Try pages = 90: Need 3 students (not enough)
- Try pages = 113: Need 2 students (just right, return 113)
Final Output:113
Time and Space Complexity
- Time Complexity: O((sum(arr) – max(arr)) * n)
For each possible max, we check all books. - Space Complexity: O(1)
Only variables for counting.
Conclusion
The brute force approach is simple and works for small inputs, but it’s too slow for large values.
Optimal Solution (Binary Search)
Intuition and Approach
We can do much better using binary search:
- Binary Search on Maximum Pages:
The answer lies between the largest single book and the total pages. Use binary search to find the minimum maximum pages. - Check If Allocation Is Possible:
For each mid value (pages), check if it’s possible to allocate books to students. - Adjust Search Window:
- If allocation is possible, try a smaller maximum.
- If not, try a larger maximum.
- Why does this work?
The allocation function is monotonic: as the maximum pages increases, it becomes easier to allocate. Binary search is perfect for this.
Code Implementation
class Solution:
def countStudents(self, nums, pages):
n = len(nums)
students = 1
pagesStudent = 0
for i in range(n):
if pagesStudent + nums[i] <= pages:
# Add pages to current student
pagesStudent += nums[i]
else:
# Add pages to next student
students += 1
pagesStudent = nums[i]
return students
def findPages(self, arr, k) -> int:
n = len(arr)
# Book allocation impossible
if k > n:
return -1
# Calculate the range for binary search
low = max(arr)
high = sum(arr)
while low <= high:
mid = (low + high) // 2
if self.countStudents(arr, mid) <= k:
high = mid - 1
else:
low = mid + 1
return lowCode Explanation
- Use binary search between the largest book and the total pages.
- For each mid value, simulate the allocation process.
- If allocation is possible, try a smaller maximum.
- If not, try a larger maximum.
- Return the minimum valid maximum found.
Dry Run
Input:arr =[12, 34, 67, 90], k = 2
- low = 90, high = 203
- mid = 146: Need 2 students (try smaller, high = 145)
- mid = 117: Need 2 students (try smaller, high = 116)
- mid = 103: Need 3 students (try larger, low = 104)
- mid = 110: Need 2 students (try smaller, high = 109)
- mid = 106: Need 3 students (try larger, low = 107)
- mid = 108: Need 3 students (try larger, low = 109)
- mid = 109: Need 3 students (try larger, low = 110)
- mid = 110: Already checked, loop ends, answer is 113
Final Output:113
Time and Space Complexity
- Time Complexity: O(n * log(sum(arr) – max(arr)))
Binary search on maximum, checking all books for each guess. - Space Complexity: O(1)
Only variables for counting.
Conclusion
The optimal solution is efficient and works well for large arrays and high values. It’s the best approach for interviews and practical use.
Final Thoughts
The “Allocate Minimum Pages” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
