Log inSign up
hardgfgNot Started

Book Allocation Problem

Given an array of books where books[i] is the number of pages in the ith book, and an integer m representing students, allocate books to all m students such that the maximum number of pages allocated to a student is minimized.

Binary Search
Solve on gfg
Lesson

Problem Statement

You are given an array arr of integers where arr[i] represents the number of pages in the i-th book. There are m students and the books need to be allocated to the m students such that: - Each student gets at least one book. - Each book is allocated to exactly one student. - The book allocation should be in contiguous order.

Allocate books such that the maximum number of pages allocated to a student is minimum. If allocation is not possible, return -1.

Example 1 · Example 1: Standard Allocation:

Input: arr = [12, 34, 67, 90], m = 2
Output: 113
Explanation: Student 1 gets [12, 34, 67] (113 pages), Student 2 gets [90] (90 pages). Max pages is 113.

Example 2 · Example 2: Impossible Allocation:

Input: arr = [25, 46, 28, 49, 24], m = 6
Output: -1
Explanation: 6 students but only 5 books, so impossible.

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i] <= 106
  • 1 <= m <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model contiguous partitioning minimax problems via binary search on answer.
  • Understand why low = max(arr) and high = sum(arr) are mathematically precise bounds.
  • Implement greedy contiguous segment accumulation in O(n).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partition array into m contiguous subarrays to minimize the maximum sum.
  • Monotonic predicate: larger capacity means fewer or equal students needed.
  • Classic minimax partitioning problem.

Algorithmic Decision Tree:

  • If m > arr.length -> return -1.
  • low = max(arr), high = sum(arr), ans = high.
  • While low <= high: mid = low + (high - low) / 2.
  • If countStudents(mid) <= m -> ans = mid, high = mid - 1.
  • Else low = mid + 1.
  • Return ans.

Connected Patterns:

Allocate Minimum Number of PagesPainter's Partition ProblemSplit Array Largest SumCapacity To Ship Packages Within D Days

1. Linear Page Limit Increment

Intuition

Loop pages from max(arr) to sum(arr). For each limit, simulate greedy student packing. Return the first limit where students <= m.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If m > arr.length return -1.
  2. Step 2: Loop limit from max(arr) to sum(arr).
  3. Step 3: If countStudents(limit) <= m return limit.
  4. Step 4: Return sum(arr).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int findPages(vector<int>& arr, int k) {
8 if (k > (int)arr.size()) return -1;
9 int low = 0, high = 0;
10 for (int x : arr) { low = max(low, x); high += x; }
11 for (int pages = low; pages <= high; ++pages) {
12 int students = 1, current = 0;
13 for (int x : arr) {
14 if (current + x > pages) {
15 students++;
16 current = 0;
17 }
18 current += x;
19 }
20 if (students <= k) return pages;
21 }
22 return high;
23}
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n * (sum(arr) - max(arr))) — Takes up to sum(arr) iterations of O(n) work each.
  • Space complexity: O(1) — O(1) memory.

2. Bounded Linear Search Starting from Average

Intuition

Mathematically, the answer cannot be less than ceil(sum(arr) / m). Starting linear scan at max(max(arr), sum/m) cuts down iterations.

When to apply: When search range is moderate.

Algorithm

  1. Step 1: If m > n return -1.
  2. Step 2: Start pages = max(max(arr), sum(arr)/m).
  3. Step 3: Test pages sequentially until countStudents(pages) <= m.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int findPages(vector<int>& arr, int k) {
8 if (k > (int)arr.size()) return -1;
9 long long sum = 0; int maxV = 0;
10 for (int x : arr) { maxV = max(maxV, x); sum += x; }
11 int start = max((long long)maxV, (sum + k - 1) / k);
12 for (int pages = start; pages <= sum; ++pages) {
13 int students = 1, current = 0;
14 for (int x : arr) {
15 if (current + x > pages) {
16 students++;
17 current = 0;
18 }
19 current += x;
20 }
21 if (students <= k) return pages;
22 }
23 return sum;
24}
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n * (sum - sum/m)) — Linear scan on the remaining domain.
  • Space complexity: O(1) — O(1) auxiliary space.

3. Binary Search on Answer Range

Intuition

If m > arr.length, return -1. Set low = max(arr), high = sum(arr), ans = high. While low <= high, compute mid. Simulate student count: if countStudents(mid) <= m, ans = mid and high = mid - 1; else low = mid + 1.

When to apply: Standard optimal solution.

Algorithm

  1. Step 1: If m > arr.length return -1.
  2. Step 2: low = max(arr), high = sum(arr), ans = high.
  3. Step 3: While low <= high:
  4. - mid = low + (high - low) / 2.
  5. - students = 1, current = 0.
  6. - For x in arr: if current + x > mid { students++; current = 0; } current += x.
  7. - If students <= m: ans = mid, high = mid - 1.
  8. - Else low = mid + 1.
  9. Step 4: Return ans.

Trace for arr = [12, 34, 67, 90], m = 2

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Range [90, 203]
Visual state
Values and pointers at this exact step
pointers
S
12
34
67
90
0
↑ low
1
2
↑ mid
3
↑ high
Check / comparison
At max pages 146: students needed = 2 <= 2 -> Feasible.
Decision / next transition
Record ans = 146, set high = 145.
Why this step matters

Range [90, 203]. mid=146. Student 1: 12+34+67 = 113 <= 146. Next book 90 exceeds 146 (113+90=203). Student 2 gets 90. Total students = 2 <= 2. Feasible! ans=146. high = mid - 1 = 145.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int findPages(vector<int>& arr, int k) {
8 if (k > (int)arr.size()) return -1;
9 long long low = 0, high = 0;
10 for (int x : arr) {
11 low = max(low, (long long)x);
12 high += x;
13 }
14 long long ans = high;
15 while (low <= high) {
16 long long mid = low + (high - low) / 2;
17 int students = 1;
18 long long current = 0;
19 for (int x : arr) {
20 if (current + x > mid) {
21 students++;
22 current = 0;
23 }
24 current += x;
25 }
26 if (students <= k) {
27 ans = mid;
28 high = mid - 1;
29 } else {
30 low = mid + 1;
31 }
32 }
33 return (int)ans;
34}
35
36int main() {
37 // Sample driver execution
38 cout << "Execution completed successfully." << endl;
39 return 0;
40}
41

Time & Space Complexity

  • Time complexity: O(n * log(sum(arr) - max(arr))) — Search space [max, sum] is bounded by 1011, taking at most 40 binary search steps of O(n) simulation.
  • Space complexity: O(1) — Requires O(1) auxiliary variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Page ScanO(n * range)O(1)Test each page limit sequentially.Iterates through all possible page sums.
2.Bounded Linear SearchO(n * range)O(1)Start from max(max, sum/m).Sequential stepping.
3.Binary Search on AnswerOptimalO(n * log(range))O(1)Binary search on monotonic capacity domain [max, sum].None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • m > n -> return -1 immediately.
  • m == 1 -> return sum(arr).
  • m == n -> return max(arr).
  • All books have the same page count.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify that 'Book Allocation Problem', 'Allocate Minimum Number of Pages', Painters Partition Problem', and 'Split Array Largest Sum' are all mathematically identical.
  2. Explain the greedy choice: filling each student's quota as much as possible without exceeding mid minimizes student count.
  3. Watch for integer overflow in sum(arr) (use long in Java/C++).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the lower bound for the binary search in the Book Allocation Problem?

Back to DSA Sheet