Allocate Minimum Pages Binary Search on Answer in DSA Javascript

Mental Model

We want to split books among students so that the largest pages assigned to any student is as small as possible. We guess a maximum pages limit and check if it works, then adjust the guess using binary search.

Analogy: Imagine you have a stack of books and a few friends. You want to give books to friends so that no one gets too many pages to read. You try a limit on pages per friend and see if you can split the books without breaking the limit. If yes, try smaller limit; if no, try bigger limit.

Books: [100] -> [200] -> [300] -> [400] -> null
Students: 2
Trying max pages limit: 500
Split: [100, 200] -> [300, 400] -> null

Dry Run Walkthrough

Input: books: [100, 200, 300, 400], students: 2

Goal: Find the minimum maximum pages assigned to any student when books are divided among 2 students

Step 1: Set low to max book pages (400), high to sum of all pages (1000), start binary search

low=400, high=1000

Why: Minimum max pages can't be less than largest book; maximum is sum of all pages

Step 2: Calculate mid = (400 + 1000) / 2 = 700; check if possible to allocate with max 700 pages

Trying max_pages=700

Why: Check feasibility with mid value to narrow search

Step 3: Allocate books: Student 1 gets 100 + 200 + 300 = 600 pages; Student 2 gets 400 pages

Allocation possible with max_pages=700

Why: Sum per student does not exceed 700, so allocation is possible

Step 4: Since allocation possible, set high = mid - 1 = 699 to try smaller max pages

low=400, high=699

Why: Try to find smaller maximum pages

Step 5: Calculate mid = (400 + 699) / 2 = 549; check allocation with max 549

Trying max_pages=549

Why: Narrow search further

Step 6: Allocate books: Student 1 gets 100 + 200 = 300 pages; Student 2 gets 300 pages; next book 400 pages can't fit in max 549 for any student

Allocation not possible with max_pages=549

Why: 400 pages book alone exceeds remaining capacity for student 2

Step 7: Since allocation not possible, set low = mid + 1 = 550

low=550, high=699

Why: Need larger max pages to fit all books

Step 8: Calculate mid = (550 + 699) / 2 = 624; check allocation with max 624

Trying max_pages=624

Why: Try mid value again

Step 9: Allocate books: Student 1 gets 100 + 200 + 300 = 600 pages; Student 2 gets 400 pages

Allocation possible with max_pages=624

Why: Sum per student does not exceed 624

Step 10: Set high = mid - 1 = 623 to try smaller max pages

low=550, high=623

Why: Try to minimize max pages further

Step 11: Calculate mid = (550 + 623) / 2 = 586; check allocation with max 586

Trying max_pages=586

Why: Narrow search

Step 12: Allocation not possible (same reason as step 6)

Allocation not possible with max_pages=586

Why: 400 pages book can't fit after previous allocations

Step 13: Set low = mid + 1 = 587

low=587, high=623

Why: Increase minimum max pages

Step 14: Calculate mid = (587 + 623) / 2 = 605; check allocation with max 605

Trying max_pages=605

Why: Try mid value

Step 15: Allocation possible: Student 1 gets 100 + 200 + 300 = 600 pages; Student 2 gets 400 pages

Allocation possible with max_pages=605

Why: Sum per student within limit

Step 16: Set high = mid - 1 = 604

low=587, high=604

Why: Try smaller max pages

Step 17: Calculate mid = (587 + 604) / 2 = 595; check allocation with max 595

Trying max_pages=595

Why: Narrow search

Step 18: Allocation not possible (same reason as step 6)

Allocation not possible with max_pages=595

Why: 400 pages book can't fit

Step 19: Set low = mid + 1 = 596

low=596, high=604

Why: Increase minimum max pages

Step 20: Calculate mid = (596 + 604) / 2 = 600; check allocation with max 600

Trying max_pages=600

Why: Try mid value

Step 21: Allocation possible: Student 1 gets 100 + 200 + 300 = 600 pages; Student 2 gets 400 pages

Allocation possible with max_pages=600

Why: Sum per student within limit

Step 22: Set high = mid - 1 = 599

low=596, high=599

Why: Try smaller max pages

Step 23: Calculate mid = (596 + 599) / 2 = 597; check allocation with max 597

Trying max_pages=597

Why: Narrow search

Step 24: Allocation not possible (same reason as step 6)

Allocation not possible with max_pages=597

Why: 400 pages book can't fit

Step 25: Set low = mid + 1 = 598

low=598, high=599

Why: Increase minimum max pages

Step 26: Calculate mid = (598 + 599) / 2 = 598; check allocation with max 598

Trying max_pages=598

Why: Try mid value

Step 27: Allocation not possible (same reason as step 6)

Allocation not possible with max_pages=598

Why: 400 pages book can't fit

Step 28: Set low = mid + 1 = 599

low=599, high=599

Why: Increase minimum max pages

Step 29: Calculate mid = (599 + 599) / 2 = 599; check allocation with max 599

Trying max_pages=599

Why: Try mid value

Step 30: Allocation not possible (same reason as step 6)

Allocation not possible with max_pages=599

Why: 400 pages book can't fit

Step 31: Set low = mid + 1 = 600

low=600, high=599

Why: low > high means search ends

Result:

Minimum maximum pages = 600
Final allocation: Student 1: [100, 200, 300], Student 2: [400]

Annotated Code

DSA Javascript

class BookAllocator {
  constructor(books, students) {
    this.books = books;
    this.students = students;
  }

  // Check if allocation possible with maxPages limit
  canAllocate(maxPages) {
    let requiredStudents = 1;
    let currentSum = 0;

    for (const pages of this.books) {
      if (pages > maxPages) return false; // single book exceeds limit

      if (currentSum + pages > maxPages) {
        requiredStudents++;
        currentSum = pages;
        if (requiredStudents > this.students) return false; // need more students
      } else {
        currentSum += pages;
      }
    }
    return true;
  }

  // Binary search to find minimum max pages
  findMinPages() {
    let low = Math.max(...this.books);
    let high = this.books.reduce((a, b) => a + b, 0);
    let result = high;

    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (this.canAllocate(mid)) {
        result = mid; // possible to allocate with mid
        high = mid - 1; // try smaller max pages
      } else {
        low = mid + 1; // need bigger max pages
      }
    }
    return result;
  }
}

// Driver code
const books = [100, 200, 300, 400];
const students = 2;
const allocator = new BookAllocator(books, students);
const minPages = allocator.findMinPages();
console.log(minPages + '');

if (pages > maxPages) return false; // single book exceeds limit

Check if any single book is larger than maxPages, making allocation impossible

if (currentSum + pages > maxPages) { requiredStudents++; currentSum = pages; if (requiredStudents > this.students) return false; }

Start new student allocation if current sum exceeds maxPages; fail if students needed exceed available

while (low <= high) { const mid = Math.floor((low + high) / 2); if (this.canAllocate(mid)) { result = mid; high = mid - 1; } else { low = mid + 1; } }

Binary search to find minimum maxPages that allows allocation

Output

600

Complexity Analysis

Time: O(n log S) because we do binary search on the sum of pages S, and each check scans all n books

Space: O(n) for storing the books array

vs Alternative: Naive approach tries all possible max pages from max book to sum, which is O(n * S) and much slower

Edge Cases

Only one book

Minimum max pages is the pages of that single book

DSA Javascript

if (pages > maxPages) return false;

Number of students equals number of books

Minimum max pages is the largest single book pages

DSA Javascript

if (pages > maxPages) return false;

Number of students is 1

Minimum max pages is sum of all book pages

DSA Javascript

let high = this.books.reduce((a, b) => a + b, 0);

When to Use This Pattern

When you need to split an array into k parts minimizing the maximum sum of parts, use binary search on the answer to efficiently find the optimal maximum sum.

Common Mistakes

Mistake: Not checking if a single book exceeds the current maxPages guess, causing wrong allocation results
Fix: Add a check to immediately return false if any single book has pages greater than maxPages

Mistake: Updating low and high incorrectly in binary search, causing infinite loops or wrong answers
Fix: Update high = mid - 1 when allocation possible, low = mid + 1 when not possible

Summary

It finds the smallest maximum number of pages assigned to any student when dividing books.

Use it when you want to split work or load evenly minimizing the maximum load.

The key insight is guessing a max pages limit and checking feasibility, then narrowing guesses with binary search.