Minimize Maximum Pages Allocated
Description
You are given an array arr[] of integers where each element arr[i] represents the number of pages in the i-th book. You are also given an integer k representing the number of students.
Your task is to allocate all the books to the students such that:
- Each student gets at least one book.
- Each book is assigned to exactly one student.
- Books are allocated in a contiguous manner — a student can only receive a consecutive sequence of books (e.g., a student cannot receive book 1 and book 3 while skipping book 2).
Among all valid allocations, find the one that minimizes the maximum total pages assigned to any single student. Return this minimized maximum value.
If it is not possible to allocate at least one book to every student (i.e., there are more students than books), return -1.
Examples
Example 1
Input: arr = [12, 34, 67, 90], k = 2
Output: 113
Explanation: There are three ways to split 4 books between 2 students (contiguously):
- [12] and [34, 67, 90] → max = 191
- [12, 34] and [67, 90] → max = 157
- [12, 34, 67] and [90] → max = 113
The third allocation gives the minimum possible maximum of 113.
Example 2
Input: arr = [15, 17, 20], k = 5
Output: -1
Explanation: There are only 3 books but 5 students. Since each student must receive at least one book, it is impossible to allocate books to all students. Return -1.
Example 3
Input: arr = [5, 17, 100, 11], k = 4
Output: 100
Explanation: With 4 books and 4 students, each student gets exactly one book: [5], [17], [100], [11]. The maximum pages any student receives is 100. This is the only valid allocation, so the answer is 100.
Constraints
- 1 ≤ arr.size() ≤ 10^6
- 1 ≤ arr[i] ≤ 10^3
- 1 ≤ k ≤ 10^3
Editorial
Brute Force
Intuition
Imagine you have a row of books on a shelf and you need to divide them among k students by placing k-1 dividers between the books. Each divider splits the row into segments, and each student gets one contiguous segment.
The brute force idea is straightforward: try every possible placement of k-1 dividers and for each placement, compute the maximum pages any student gets. Track the minimum across all placements.
For n books and k students, we need to choose k-1 positions out of the n-1 possible gaps between consecutive books. This is a classic combinations problem: C(n-1, k-1) total configurations. For each configuration, we compute the page sums of all segments and take the maximum.
This approach is correct but computationally explosive — with n up to 10^6, even generating all combinations is infeasible.
Step-by-Step Explanation
Let's trace through with arr = [12, 34, 67, 90], k = 2:
We need to place 1 divider among 3 possible gaps.
Step 1: Initialize. We have 4 books, 2 students, so we need k-1 = 1 divider. The possible gap positions are after index 0, 1, or 2.
Step 2: Place divider after index 0: Segments = [12] and [34, 67, 90]. Sums = [12, 191]. Max = 191.
Step 3: Place divider after index 1: Segments = [12, 34] and [67, 90]. Sums = [46, 157]. Max = 157.
Step 4: Place divider after index 2: Segments = [12, 34, 67] and [90]. Sums = [113, 90]. Max = 113.
Step 5: Compare all maximums: min(191, 157, 113) = 113.
Step 6: Return 113.
Brute Force — Try Every Divider Placement — Watch as we place a divider at each possible gap, compute segment sums, and track the minimum of the maximums.
Algorithm
- If k > n, return -1 (more students than books)
- Generate all C(n-1, k-1) ways to place k-1 dividers in the n-1 gaps
- For each placement:
a. Compute the sum of pages in each of the k segments
b. Record the maximum segment sum - Return the minimum over all recorded maximums
Code
class Solution {
public:
int ans;
void solve(vector<int>& arr, int k, int idx, vector<int>& dividers) {
if ((int)dividers.size() == k - 1) {
// Compute segment sums
int maxPages = 0;
int prev = 0;
vector<int> cuts = dividers;
cuts.push_back(arr.size());
for (int cut : cuts) {
int sum = 0;
for (int i = prev; i < cut; i++) sum += arr[i];
maxPages = max(maxPages, sum);
prev = cut;
}
ans = min(ans, maxPages);
return;
}
int start = dividers.empty() ? 1 : dividers.back() + 1;
for (int i = start; i < (int)arr.size(); i++) {
dividers.push_back(i);
solve(arr, k, i + 1, dividers);
dividers.pop_back();
}
}
int findPages(vector<int>& arr, int k) {
int n = arr.size();
if (k > n) return -1;
ans = INT_MAX;
vector<int> dividers;
solve(arr, k, 0, dividers);
return ans;
}
};from itertools import combinations
class Solution:
def findPages(self, arr, k):
n = len(arr)
if k > n:
return -1
best = float('inf')
# Choose k-1 divider positions from gaps 1..n-1
for dividers in combinations(range(1, n), k - 1):
cuts = [0] + list(dividers) + [n]
max_pages = 0
for i in range(len(cuts) - 1):
segment_sum = sum(arr[cuts[i]:cuts[i + 1]])
max_pages = max(max_pages, segment_sum)
best = min(best, max_pages)
return bestimport java.util.*;
class Solution {
int ans;
void solve(int[] arr, int k, int idx, List<Integer> dividers) {
if (dividers.size() == k - 1) {
List<Integer> cuts = new ArrayList<>(dividers);
cuts.add(arr.length);
int maxPages = 0, prev = 0;
for (int cut : cuts) {
int sum = 0;
for (int i = prev; i < cut; i++) sum += arr[i];
maxPages = Math.max(maxPages, sum);
prev = cut;
}
ans = Math.min(ans, maxPages);
return;
}
int start = dividers.isEmpty() ? 1 : dividers.get(dividers.size() - 1) + 1;
for (int i = start; i < arr.length; i++) {
dividers.add(i);
solve(arr, k, i + 1, dividers);
dividers.remove(dividers.size() - 1);
}
}
public int findPages(int[] arr, int k) {
int n = arr.length;
if (k > n) return -1;
ans = Integer.MAX_VALUE;
solve(arr, k, 0, new ArrayList<>());
return ans;
}
}Complexity Analysis
Time Complexity: O(C(n-1, k-1) × n)
We generate all C(n-1, k-1) combinations of divider placements. For each combination, computing the segment sums takes O(n). The number of combinations can be exponential — C(n-1, k-1) grows extremely fast. For example, with n=20 and k=10, C(19,9) = 92,378 combinations.
Space Complexity: O(k)
We store up to k-1 divider positions in the recursion stack. The recursion depth is at most k-1.
Why This Approach Is Not Efficient
The brute force approach generates all C(n-1, k-1) divider placements, which grows exponentially. With n up to 10^6 and k up to 10^3, this is astronomically large — far beyond any time limit.
The fundamental issue is that we're searching over an enormous combinatorial space when we don't need to. Instead of asking "where should I place the dividers?", we can flip the question: "if I cap every student at X pages, can I distribute all books among k students?"
This reframing transforms the problem from a combinatorial search into a decision problem: given a page limit X, is the allocation feasible? If we can answer this efficiently, we can search for the smallest feasible X instead of trying all possible partition configurations.
The answer space for X is bounded: the minimum possible value is max(arr) (the largest single book — since some student must read it), and the maximum is sum(arr) (one student reads everything). We can linearly scan through this range and use a greedy feasibility check.
Better Approach - Linear Search on Answer
Intuition
Instead of trying every way to partition the books, let's think about the answer itself. The answer is some number X — the maximum pages any student reads. What are the possible values of X?
- Minimum possible X: max(arr). No matter how we split, at least one student must read the largest book. So X ≥ max(arr).
- Maximum possible X: sum(arr). If only one student reads all books, X = sum(arr).
For any candidate value X, we can check if it's feasible using a greedy strategy: scan from left to right, assigning books to the current student as long as adding the next book doesn't exceed X pages. When it would exceed X, start a new student. If we finish using ≤ k students, X is feasible.
The key observation: if X is feasible, then X+1 is also feasible (more room per student). And if X is too small, X-1 is also too small. This means there's a threshold — we want the smallest X that's feasible.
In this approach, we try every X from max(arr) to sum(arr) and return the first feasible one.
Step-by-Step Explanation
Let's trace through with arr = [12, 34, 67, 90], k = 2:
min X = max(arr) = 90, max X = sum(arr) = 203.
Step 1: Try X = 90. Greedy allocation:
- Student 1: 12 (total 12). Add 34? 12+34=46 ≤ 90. Add 67? 46+67=113 > 90. Stop. Student 1 gets [12, 34] = 46.
- Student 2: 67 (total 67). Add 90? 67+90=157 > 90. Stop. Student 2 gets [67] = 67.
- Student 3: 90. But we only have k=2 students! Need 3 students → NOT feasible.
Step 2: Try X = 91...112 (all fail similarly — the gap 67+90=157 still exceeds these limits). Let me skip to X = 113.
Step 3: Try X = 113. Greedy allocation:
- Student 1: 12 (total 12). Add 34? 46 ≤ 113. Add 67? 113 ≤ 113. Add 90? 203 > 113. Stop. Student 1 gets [12, 34, 67] = 113.
- Student 2: 90 (total 90). No more books. Student 2 gets [90] = 90.
- Used 2 students ≤ k=2 → FEASIBLE!
Step 4: Return 113 (the first feasible value).
Linear Search — Testing Candidate Page Limits — Watch as we test increasing page limits from max(arr) upward, using the greedy feasibility check until we find the smallest feasible value.
Algorithm
- If k > n, return -1
- Set lo = max(arr), hi = sum(arr)
- For each candidate X from lo to hi:
a. Run greedy feasibility check:- Scan left to right, accumulating pages for current student
- If adding next book exceeds X, start a new student
- Count total students needed
b. If students needed ≤ k, return X (first feasible value)
- Return hi (always feasible as a fallback)
Code
class Solution {
public:
bool canAllocate(vector<int>& arr, int k, int maxPages) {
int students = 1;
int currentSum = 0;
for (int pages : arr) {
if (currentSum + pages > maxPages) {
students++;
currentSum = pages;
} else {
currentSum += pages;
}
}
return students <= k;
}
int findPages(vector<int>& arr, int k) {
int n = arr.size();
if (k > n) return -1;
int lo = *max_element(arr.begin(), arr.end());
int hi = accumulate(arr.begin(), arr.end(), 0);
for (int x = lo; x <= hi; x++) {
if (canAllocate(arr, k, x)) {
return x;
}
}
return hi;
}
};class Solution:
def findPages(self, arr, k):
n = len(arr)
if k > n:
return -1
def can_allocate(max_pages):
students = 1
current_sum = 0
for pages in arr:
if current_sum + pages > max_pages:
students += 1
current_sum = pages
else:
current_sum += pages
return students <= k
lo = max(arr)
hi = sum(arr)
for x in range(lo, hi + 1):
if can_allocate(x):
return x
return hiimport java.util.*;
class Solution {
boolean canAllocate(int[] arr, int k, int maxPages) {
int students = 1;
int currentSum = 0;
for (int pages : arr) {
if (currentSum + pages > maxPages) {
students++;
currentSum = pages;
} else {
currentSum += pages;
}
}
return students <= k;
}
public int findPages(int[] arr, int k) {
int n = arr.length;
if (k > n) return -1;
int lo = Arrays.stream(arr).max().getAsInt();
int hi = Arrays.stream(arr).sum();
for (int x = lo; x <= hi; x++) {
if (canAllocate(arr, k, x)) {
return x;
}
}
return hi;
}
}Complexity Analysis
Time Complexity: O((sum(arr) - max(arr)) × n)
We iterate through at most sum(arr) - max(arr) + 1 candidate values. For each, the greedy feasibility check scans all n elements. With arr[i] up to 10^3 and n up to 10^6, sum(arr) can be up to 10^9, making this approach potentially 10^9 × 10^6 = 10^15 operations — far too slow.
Space Complexity: O(1)
Only a few integer variables are used.
Why This Approach Is Not Efficient
The linear search iterates through up to sum(arr) - max(arr) candidate values. With arr[i] up to 10^3 and n up to 10^6, the sum can reach 10^9. Scanning from max(arr) to sum(arr) means up to ~10^9 iterations, each costing O(n) for the feasibility check — a total of up to 10^15 operations.
But here's the critical insight we're underusing: the feasibility function canAllocate(X) is monotonic. Once X is large enough to be feasible, every larger value is also feasible. And below the threshold, every smaller value is infeasible.
This false-to-true transition is exactly the pattern where binary search excels. Instead of scanning linearly through the answer space, we can binary search: check the midpoint, eliminate half the range, and converge in O(log(sum - max)) steps instead of O(sum - max) steps. This turns 10^9 iterations into about 30.
Optimal Approach - Binary Search on Answer
Intuition
We binary search on the answer itself — the maximum pages any student reads.
The answer space is [max(arr), sum(arr)]. For any candidate value mid:
- Run the greedy feasibility check: scan books left to right, assigning to the current student until adding the next book would exceed
mid. When it does, start a new student. - If we need ≤ k students,
midis feasible → try a smaller value (go left) - If we need > k students,
midis too small → try a larger value (go right)
The greedy check works because the books must be contiguous: we simply pack as many books as possible per student without exceeding the limit, which minimizes the number of students needed. If even this greedy-optimal packing exceeds k students, no valid allocation exists for that limit.
Binary search converges in O(log(sum - max)) iterations, each costing O(n) for the feasibility check. This gives us O(n × log(sum)) total — efficient enough for n up to 10^6.
Step-by-Step Explanation
Let's trace through with arr = [12, 34, 67, 90], k = 2:
Search space: lo = max(arr) = 90, hi = sum(arr) = 203.
Step 1: Initialize lo = 90, hi = 203.
Step 2: mid = (90 + 203) / 2 = 146. Check feasibility:
- Student 1: 12+34+67 = 113 ≤ 146. Add 90? 203 > 146. Stop. Student 1 = [12,34,67].
- Student 2: 90 ≤ 146. Done. Students used = 2 ≤ k.
- Feasible! Answer could be 146 or smaller. Set hi = 146.
Step 3: lo = 90, hi = 146, mid = (90 + 146) / 2 = 118. Check feasibility:
- Student 1: 12+34+67 = 113 ≤ 118. Add 90? 203 > 118. Stop. Student 1 = [12,34,67].
- Student 2: 90 ≤ 118. Done. Students used = 2 ≤ k.
- Feasible! Set hi = 118.
Step 4: lo = 90, hi = 118, mid = (90 + 118) / 2 = 104. Check feasibility:
- Student 1: 12+34 = 46 ≤ 104. Add 67? 113 > 104. Stop. Student 1 = [12,34].
- Student 2: 67. Add 90? 157 > 104. Stop. Student 2 = [67].
- Student 3: 90. Students used = 3 > k.
- NOT feasible! Set lo = 105.
Step 5: lo = 105, hi = 118, mid = (105 + 118) / 2 = 111. Check feasibility:
- Student 1: 12+34+67 = 113 > ... wait: 12+34 = 46 ≤ 111. Add 67? 113 > 111. Stop. Student 1 = [12,34].
- Student 2: 67. Add 90? 157 > 111. Stop. Student 2 = [67].
- Student 3: 90. Students = 3 > k.
- NOT feasible! Set lo = 112.
Step 6: lo = 112, hi = 118, mid = (112 + 118) / 2 = 115. Check feasibility:
- Student 1: 12+34+67 = 113 ≤ 115. Add 90? 203 > 115. Stop.
- Student 2: 90. Students = 2 ≤ k.
- Feasible! Set hi = 115.
Step 7: lo = 112, hi = 115, mid = 113. Check feasibility:
- Student 1: 12+34+67 = 113 ≤ 113. Add 90? 203 > 113. Stop.
- Student 2: 90. Students = 2 ≤ k.
- Feasible! Set hi = 113.
Step 8: lo = 112, hi = 113, mid = 112. Check feasibility:
- Student 1: 12+34 = 46 ≤ 112. Add 67? 113 > 112. Stop.
- Student 2: 67. Add 90? 157 > 112. Stop.
- Student 3: 90. Students = 3 > k.
- NOT feasible! Set lo = 113.
Step 9: lo = 113 > hi = 113. Loop ends. lo = hi = 113.
Step 10: Return 113.
Binary Search on Answer — Halving the Page Limit Range — Watch binary search narrow the range [max(arr), sum(arr)] by testing the midpoint's feasibility with a greedy allocation check.
Algorithm
- If k > n, return -1
- Set lo = max(arr), hi = sum(arr)
- While lo < hi:
a. Compute mid = lo + (hi - lo) / 2
b. Run greedy feasibility check with page limit = mid:- Count students needed by greedily assigning contiguous books
c. If feasible (students ≤ k): hi = mid
d. If not feasible (students > k): lo = mid + 1
- Count students needed by greedily assigning contiguous books
- Return lo
Code
class Solution {
public:
bool canAllocate(vector<int>& arr, int k, int maxPages) {
int students = 1;
int currentSum = 0;
for (int pages : arr) {
if (currentSum + pages > maxPages) {
students++;
currentSum = pages;
} else {
currentSum += pages;
}
}
return students <= k;
}
int findPages(vector<int>& arr, int k) {
int n = arr.size();
if (k > n) return -1;
int lo = *max_element(arr.begin(), arr.end());
int hi = accumulate(arr.begin(), arr.end(), 0);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canAllocate(arr, k, mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
};class Solution:
def findPages(self, arr, k):
n = len(arr)
if k > n:
return -1
def can_allocate(max_pages):
students = 1
current_sum = 0
for pages in arr:
if current_sum + pages > max_pages:
students += 1
current_sum = pages
else:
current_sum += pages
return students <= k
lo = max(arr)
hi = sum(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_allocate(mid):
hi = mid
else:
lo = mid + 1
return loimport java.util.*;
class Solution {
boolean canAllocate(int[] arr, int k, int maxPages) {
int students = 1;
int currentSum = 0;
for (int pages : arr) {
if (currentSum + pages > maxPages) {
students++;
currentSum = pages;
} else {
currentSum += pages;
}
}
return students <= k;
}
public int findPages(int[] arr, int k) {
int n = arr.length;
if (k > n) return -1;
int lo = Arrays.stream(arr).max().getAsInt();
int hi = Arrays.stream(arr).sum();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canAllocate(arr, k, mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}Complexity Analysis
Time Complexity: O(n × log(sum(arr)))
Binary search runs O(log(sum(arr) - max(arr))) iterations. Since sum(arr) ≤ n × max_val ≤ 10^6 × 10^3 = 10^9, this is at most log₂(10^9) ≈ 30 iterations. Each iteration runs the O(n) greedy feasibility check. Total: O(30 × n) = O(n × log(sum)).
For n = 10^6, this is about 3 × 10^7 operations — well within time limits.
Space Complexity: O(1)
Only a few integer variables (lo, hi, mid, students, currentSum) are used. The greedy check is done in-place with no auxiliary data structures.