Allocate Minimum Pages to Students - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

You are given a list of N books where each book has a certain number of pages, and you have to allocate these books to M students.

Your goal is to distribute the books among students in such a way that:

  • Each student gets at least one book.
  • Each book is allocated to exactly one student.
  • Books allocated to a student must be in a contiguous block (i.e., no skipping).

The task is to minimize the maximum number of pages assigned to a student across all students.

If it is not possible to allocate the books as per the rules, return -1.

Examples❯

Books (Pages) Students Output Description
[10, 20, 30, 40] 2 60 Allocate [10, 20, 30] to one student and [40] to another → max pages = 60
[12, 34, 67, 90] 2 113 Best allocation: [12, 34, 67] and [90] → max = 113
[5, 17, 100, 11] 4 100 Each student gets one book → max = 100
[10, 20, 30, 40] 5 -1 More students than books → allocation not possible
[100] 1 100 Only one book and one student → give full book
[50, 60] 1 110 One student must take all books → total = 110
[] 1 -1 Empty book list → cannot allocate
[15, 25, 35] 0 -1 No students to allocate → invalid input

Solution❯

Understanding the Problem

We are given an array where each element represents the number of pages in a book. Our goal is to assign these books to a given number of students such that:

  • Each student gets at least one book.
  • Books are assigned in contiguous blocks (no skipping allowed).
  • We minimize the maximum number of pages assigned to any student.

This is a classic allocation problem where we want to fairly distribute the load. The fairness is measured by how low we can keep the highest page count that any single student gets.

Step-by-Step Solution with Example

Step 1: Understand the Inputs and Outputs

Suppose we have the books [12, 34, 67, 90] and we want to assign them to 2 students.

Each student must receive a continuous block of books. We must split this array into two parts such that the student who reads the most pages still reads as little as possible.

Step 2: Identify the Search Range

We use binary search between:

  • low = max(arr) → No student can get less than the largest book.
  • high = sum(arr) → One student takes all books.

For our example, low = 90, high = 203.

Step 3: Apply Binary Search to Minimize the Maximum Pages

We try to find the minimum value of the maximum pages a student reads. At each step, we pick mid = (low + high) // 2 and check:

Can we divide books into ≤ k students so that no one gets more than mid pages?

If yes, we try to find a smaller value. If not, we search higher.

Step 4: Write a Helper Function to Check Feasibility

We count how many students are needed if each student is allowed a maximum of mid pages. We go through the books, summing their pages until we exceed mid, then assign to a new student.

Step 5: Apply the Logic with Our Example

Try mid = 120. Can we divide books so no student gets more than 120 pages?

  • Student 1 → 12 + 34 + 67 = 113 (OK)
  • Student 2 → 90 (OK)

This is valid. Try smaller value to minimize max pages.

Step 6: Find the Minimum Possible Maximum

Keep repeating until low > high. The lowest mid for which allocation is possible is the answer.

In this example, the answer would be 113 — that’s the least maximum load possible.

Edge Cases

  • Empty book list — Nothing to assign → return -1.
  • Zero students — No one to assign → return -1.
  • More students than books — Not possible to assign at least one book per student → return -1.
  • One student — Must read all books → return sum(arr).
  • Equal books and students — Each gets one → return max(arr).

Finally

This problem is best solved using binary search on the answer range. By narrowing down the maximum number of pages a student can take, and validating it efficiently, we avoid brute force.

Always remember to handle edge cases up front, and make sure your solution respects the constraints: contiguous blocks and at least one book per student.

This is a perfect example of optimization under constraints — a very common pattern in algorithm design!

Algorithm Steps❯

  1. Set low = max(arr) and high = sum(arr).
  2. While low ≤ high, do:
  3. → Calculate mid = (low + high) / 2.
  4. → Check if it's possible to allocate books so that no student has more than mid pages using a helper function.
  5. → If possible, store the result and try to reduce it: high = mid - 1.
  6. → If not possible, increase the range: low = mid + 1.
  7. Return the minimum value found that satisfies the condition.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int isPossible(int arr[], int n, int m, int maxPages) {
    int students = 1, pages = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxPages) return 0;
        if (pages + arr[i] > maxPages) {
            students++;
            pages = arr[i];
        } else {
            pages += arr[i];
        }
    }
    return students <= m;
}

int findMinimumPages(int arr[], int n, int m) {
    if (m > n) return -1;
    int low = arr[0], high = 0, result = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] > low) low = arr[i];
        high += arr[i];
    }
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isPossible(arr, n, m, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int arr[] = {12, 34, 67, 90};
    int students = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Minimum Maximum Pages: %d\n", findMinimumPages(arr, n, students));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)Occurs if binary search hits the correct answer in the first try, but validation still needs to check all books.
Average CaseO(n * log(sum - max))Binary search over range from max(arr) to sum(arr), and for each guess, we iterate through n books.
Worst CaseO(n * log(sum - max))Even in the worst case, we perform log iterations and n-time validation per iteration.

Space Complexity❯

O(1)

Explanation: Only a fixed number of variables are used. No extra space is needed.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...