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.

Practice

1. What is the main goal of the Allocate Minimum Pages problem using binary search on answer?

easy

A. To assign pages randomly among students

B. To maximize the total number of pages assigned

C. To find the average number of pages per student

D. To minimize the maximum number of pages assigned to a student

Solution

1. Step 1: Understand the problem objective

   The problem asks to allocate books to students such that the maximum pages assigned to any student is minimized.

2. Step 2: Identify the binary search approach

   We use binary search on the range of possible maximum pages to find the minimum feasible maximum.

3. Final Answer:

   To minimize the maximum number of pages assigned to a student -> Option D

4. Quick Check:

   Goal = minimize max pages [OK]

Hint: Minimize max pages per student using binary search [OK]

Common Mistakes:

• Trying to maximize pages instead of minimizing
• Ignoring the maximum pages constraint
• Confusing total pages with max pages per student

2. Which of the following is the correct TypeScript syntax to declare the binary search boundaries for the Allocate Minimum Pages problem given an array pages?

easy

A. let low = pages.length; let high = Math.max(...pages);

B. let low = Math.min(...pages); let high = pages.length;

C. let low = 0; let high = pages.reduce((a, b) => a + b, 0);

D. let low = 0; let high = Math.min(...pages);

Solution

1. Step 1: Determine low and high boundaries

   Low is minimum possible max pages (0 or max single book pages), high is sum of all pages (max total pages).

2. Step 2: Check correct syntax for sum

   Using reduce sums all pages correctly for high boundary.

3. Final Answer:

   let low = 0; let high = pages.reduce((a, b) => a + b, 0); -> Option C

4. Quick Check:

   low = 0, high = sum pages [OK]

Hint: Sum array for high, zero or max page for low [OK]

Common Mistakes:

• Setting low as pages.length instead of page count
• Using min pages as high boundary
• Incorrect sum calculation syntax

3. Consider the following TypeScript code snippet for checking feasibility in Allocate Minimum Pages problem:

function isPossible(pages: number[], students: number, maxPages: number): boolean {
  let requiredStudents = 1;
  let currentSum = 0;
  for (let page of pages) {
    if (page > maxPages) return false;
    if (currentSum + page > maxPages) {
      requiredStudents++;
      currentSum = page;
    } else {
      currentSum += page;
    }
  }
  return requiredStudents <= students;
}

What is the output of isPossible([10, 20, 30, 40], 2, 50)?

medium

A. false

B. SyntaxError

C. true

D. RuntimeError

Solution

1. Step 1: Trace allocation with maxPages = 50

   Assign pages: 10+20=30 (still <=50), add 30 would exceed 50, so new student starts with 30, then 40 exceeds 50 if added, so new student starts with 40.

2. Step 2: Count required students

   We used 3 students but only 2 allowed, so requiredStudents=3 > 2 means return false. But check carefully: 10+20=30, next 30 alone fits in second student, 40 alone needs third student.

3. Final Answer:

   false -> Option A

4. Quick Check:

   Required students = 3 > 2, so false [OK]

Hint: Count students needed, compare with allowed [OK]

Common Mistakes:

• Ignoring that a single book can exceed maxPages
• Miscounting students when sum exceeds maxPages
• Assuming sum of all pages fits in one student

4. The following TypeScript function attempts to find the minimum maximum pages but has a bug. Identify the bug.

function findMinPages(pages: number[], students: number): number {
  let low = Math.min(...pages);
  let high = pages.reduce((a, b) => a + b, 0);
  let result = high;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (isPossible(pages, students, mid)) {
      result = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return result;
}

medium

A. High should be min page, not sum of pages

B. Low should start from max page, not min page

C. Mid calculation causes infinite loop

D. Result variable is not updated

Solution

1. Step 1: Analyze low boundary initialization

   Low should be the maximum single book pages, because no student can get less than the largest book.

2. Step 2: Identify impact of wrong low

   Starting low at minimum page can cause incorrect feasibility checks and longer search.

3. Final Answer:

   Low should start from max page, not min page -> Option B

4. Quick Check:

   Low = max page [OK]

Hint: Low boundary = max single book pages [OK]

Common Mistakes:

• Setting low to min page instead of max page
• Confusing high boundary with low
• Not updating result inside loop

5. Given books with pages [12, 34, 67, 90] and 3 students, what is the minimum maximum pages allocated to any student using binary search on answer?

hard

A. 90

B. 113

C. 67

D. 34

Solution

1. Step 1: Set search boundaries

   Low = max pages = 90, High = sum pages = 12+34+67+90=203.

2. Step 2: Binary search feasibility checks

   Mid = (90+203)//2=146. Check if possible with maxPages=146: allocate [12+34+67=113] to student1, 90 to student2, only 2 students needed <=3, possible. So high=145.

3. Step 3: Narrow down to minimum max pages

   Continuing: mid=103 possible [12+34=46,67,90] 3 students. mid=96 possible. mid=92 possible. mid=90: [12+34=46], [67], [90] all <=90, 3 students <=3 feasible, high=89. Loop ends with result=90.

4. Step 4: Re-evaluate minimum max pages

   Check if 113 is feasible with 3 students: [12+34+67=113], [90] 2 students needed <=3, so 113 is feasible but not minimum.

5. Step 5: Check if 90 is feasible

   Allocations: [12+34=46], [67], [90] 3 students needed <=3, feasible.

6. Final Answer:

   90 -> Option A

7. Quick Check:

   Minimum max pages = 90 [OK]

Hint: Binary search between max page and sum pages [OK]

Common Mistakes:

• Misallocating at max=90 thinking 4 students needed
• Miscounting students during allocation
• Confusing with 2 students (113)