Allocate Minimum Pages Binary Search on Answer in DSA Typescript

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, adjusting guesses using binary search.

Analogy: Imagine you have a pile of books and some friends. You want to give books to friends so that no one gets too many pages. You try a guess for the max pages one friend can get, then see if you can divide books without breaking that guess. If yes, try smaller guess; if no, try bigger guess.

Books: [100] -> [200] -> [300] -> [400] -> [500] -> null
Students: 3
Guess max pages: 500
Allocation example:
Student1: 100 -> 200 -> null
Student2: 300 -> null
Student3: 400 -> 500 -> null

Dry Run Walkthrough

Input: books pages: [100, 200, 300, 400, 500], students: 3

Goal: Find the smallest maximum pages assigned to any student when books are divided in order among 3 students

Step 1: Set low to max book pages (500), high to sum of all pages (1500), mid = (500+1500)//2 = 1000

low=500, mid=1000, high=1500

Why: We start binary search between max single book and total pages

Step 2: Check if we can allocate books with max pages per student = 1000

Allocation: Student1: 100+200+300=600 ≤1000, Student2: 400 ≤1000, Student3: 500 ≤1000

Why: 1000 is enough to allocate all books to 3 students

Step 3: Since allocation possible, try smaller max: high = mid - 1 = 999

low=500, high=999

Why: Try to find smaller max pages to minimize maximum

Step 4: Calculate new mid = (500+999)//2 = 749

low=500, mid=749, high=999

Why: Check feasibility with smaller max pages

Step 5: Check allocation with max pages = 749

Student1: 100+200+300=600 ≤749, Student2: 400 ≤749, Student3: 500 ≤749

Why: Allocation still possible with 749 max pages

Step 6: Try smaller max again: high = mid - 1 = 748

low=500, high=748

Why: Try to minimize max pages further

Step 7: Calculate mid = (500+748)//2 = 624

low=500, mid=624, high=748

Why: Check feasibility with 624 max pages

Step 8: Check allocation with max pages = 624

Student1: 100+200+300=600 ≤624, Student2: 400 ≤624, Student3: 500 ≤624

Why: Allocation possible with 624 max pages

Step 9: Try smaller max: high = mid - 1 = 623

low=500, high=623

Why: Try to minimize max pages further

Step 10: Calculate mid = (500+623)//2 = 561

low=500, mid=561, high=623

Why: Check feasibility with 561 max pages

Step 11: Check allocation with max pages = 561

Student1: 100+200=300 ≤561, Student2: 300+400=700 >561 (not allowed), allocation fails

Why: Cannot allocate all books within 561 max pages

Step 12: Increase low: low = mid + 1 = 562

low=562, high=623

Why: Try larger max pages since 561 failed

Step 13: Calculate mid = (562+623)//2 = 592

low=562, mid=592, high=623

Why: Check feasibility with 592 max pages

Step 14: Check allocation with max pages = 592

Student1: 100+200=300 ≤592, Student2: 300+400=700 >592 (fail)

Why: Allocation fails again with 592 max pages

Step 15: Increase low: low = mid + 1 = 593

low=593, high=623

Why: Try larger max pages

Step 16: Calculate mid = (593+623)//2 = 608

low=593, mid=608, high=623

Why: Check feasibility with 608 max pages

Step 17: Check allocation with max pages = 608

Student1: 100+200=300 ≤608, Student2: 300+400=700 >608 (fail)

Why: Allocation fails again

Step 18: Increase low: low = mid + 1 = 609

low=609, high=623

Why: Try larger max pages

Step 19: Calculate mid = (609+623)//2 = 616

low=609, mid=616, high=623

Why: Check feasibility with 616 max pages

Step 20: Check allocation with max pages = 616

Student1: 100+200=300 ≤616, Student2: 300+400=700 >616 (fail)

Why: Allocation fails again

Step 21: Increase low: low = mid + 1 = 617

low=617, high=623

Why: Try larger max pages

Step 22: Calculate mid = (617+623)//2 = 620

low=617, mid=620, high=623

Why: Check feasibility with 620 max pages

Step 23: Check allocation with max pages = 620

Student1: 100+200=300 ≤620, Student2: 300+400=700 >620 (fail)

Why: Allocation fails again

Step 24: Increase low: low = mid + 1 = 621

low=621, high=623

Why: Try larger max pages

Step 25: Calculate mid = (621+623)//2 = 622

low=621, mid=622, high=623

Why: Check feasibility with 622 max pages

Step 26: Check allocation with max pages = 622

Student1: 100+200=300 ≤622, Student2: 300+400=700 >622 (fail)

Why: Allocation fails again

Step 27: Increase low: low = mid + 1 = 623

low=623, high=623

Why: Try larger max pages

Step 28: Check allocation with max pages = 623

Student1: 100+200+300=600 ≤623, Student2: 400 ≤623, Student3: 500 ≤623

Why: Allocation possible at 623 max pages

Step 29: Since low == high, binary search ends with answer = 623

low=623, high=623

Why: Found minimum max pages for allocation

Result:

Final allocation max pages = 623
Books allocation example:
Student1: 100 -> 200 -> 300 -> null
Student2: 400 -> null
Student3: 500 -> null

Annotated Code

DSA Typescript

class AllocateMinimumPages {
  static canAllocate(books: number[], students: number, maxPages: number): boolean {
    let requiredStudents = 1;
    let currentSum = 0;
    for (const pages of books) {
      if (pages > maxPages) return false; // single book exceeds maxPages
      if (currentSum + pages > maxPages) {
        requiredStudents++;
        currentSum = pages;
        if (requiredStudents > students) return false; // need more students than available
      } else {
        currentSum += pages;
      }
    }
    return true;
  }

  static findMinimumPages(books: number[], students: number): number {
    let low = Math.max(...books);
    let high = books.reduce((a, b) => a + b, 0);
    let result = high;

    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (this.canAllocate(books, students, mid)) {
        result = mid;
        high = mid - 1; // try smaller max pages
      } else {
        low = mid + 1; // increase max pages
      }
    }
    return result;
  }
}

// Driver code
const books = [100, 200, 300, 400, 500];
const students = 3;
const minPages = AllocateMinimumPages.findMinimumPages(books, students);
console.log(minPages);

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

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

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

Start new student allocation if adding current book exceeds maxPages; fail if too many students needed

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

Binary search on maxPages: narrow down to smallest feasible maxPages

Output

623

Complexity Analysis

Time: O(n log S) where n is number of books and S is sum of pages because binary search runs log S times and each feasibility check takes O(n)

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach tries all possible max pages from max book to sum, which is O(n*S) and too slow; binary search reduces this to O(n log S)

Edge Cases

Only one student

All books must be allocated to that student; max pages is sum of all books

DSA Typescript

if (requiredStudents > students) return false;

Number of students equals number of books

Each student gets exactly one book; max pages is max single book pages

DSA Typescript

if (pages > maxPages) return false;

Book with pages larger than any guess

Allocation impossible; function returns false immediately

DSA Typescript

if (pages > maxPages) return false;

When to Use This Pattern

When asked to split an array into subarrays minimizing the maximum sum among them, use binary search on the answer combined with a feasibility check to find the optimal maximum sum.

Common Mistakes

Mistake: Not checking if a single book exceeds the current maxPages guess, leading to incorrect feasibility results
Fix: Add a check to immediately return false if any single book has more pages than maxPages

Mistake: Not updating the current sum correctly when starting allocation for a new student
Fix: Reset currentSum to current book pages when moving to next student

Mistake: Using high = mid instead of high = mid - 1 when allocation is possible, causing infinite loop
Fix: Use high = mid - 1 to shrink search space properly

Summary

It finds the smallest maximum pages assigned to any student when dividing books in order.

Use it when you need to split an array into parts minimizing the largest sum part.

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