Allocate Minimum Pages Binary Search on Answer in DSA Go

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 we can allocate books within that limit.

Analogy: Imagine dividing a pile of books among friends so that no one carries too many pages. You try a weight limit and see if everyone can carry their share without exceeding it.

Books: [100] -> [200] -> [300] -> [400] -> null
Students: 2
Trying max pages limit: 500
Allocation example:
Student 1: 100 -> 200 -> 300 (total 600 > 500 not allowed)
Student 2: 400
So 500 is too small, try bigger limit.

Dry Run Walkthrough

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

Goal: Find the minimum maximum pages any student has to read 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, max can't be more than total pages

Step 2: Check mid = (400+1000)/2 = 700, try to allocate books with max pages 700

Try allocation with max_pages=700

Why: Test if 700 is a valid max pages limit

Step 3: Allocate books: Student 1 gets 100+200+300=600 (<=700), Student 2 gets 400 (<=700)

Allocation possible with max_pages=700

Why: 700 works, try smaller max to minimize

Step 4: Set high = mid - 1 = 699, binary search continues

low=400, high=699

Why: Try smaller max pages to find minimum

Step 5: Check mid = (400+699)/2 = 549, try allocation with max pages 549

Try allocation with max_pages=549

Why: Test if 549 is valid max pages limit

Step 6: Allocate books: Student 1 gets 100+200=300 (<=549), next book 300 would exceed 549, so Student 2 gets 300+400=700 (>549) not allowed

Allocation not possible with max_pages=549

Why: 549 too small, need bigger max pages

Step 7: Set low = mid + 1 = 550, binary search continues

low=550, high=699

Why: Increase max pages to allow allocation

Step 8: Check mid = (550+699)/2 = 624, try allocation with max pages 624

Try allocation with max_pages=624

Why: Test if 624 is valid max pages limit

Step 9: Allocate books: Student 1 gets 100+200+300=600 (<=624), Student 2 gets 400 (<=624)

Allocation possible with max_pages=624

Why: 624 works, try smaller max

Step 10: Set high = mid - 1 = 623, binary search continues

low=550, high=623

Why: Try smaller max pages

Step 11: Check mid = (550+623)/2 = 586, try allocation with max pages 586

Try allocation with max_pages=586

Why: Test if 586 is valid max pages limit

Step 12: Allocate books: Student 1 gets 100+200=300 (<=586), next book 300 would exceed 586, Student 2 gets 300+400=700 (>586) not allowed

Allocation not possible with max_pages=586

Why: 586 too small

Step 13: Set low = mid + 1 = 587, binary search continues

low=587, high=623

Why: Increase max pages

Step 14: Check mid = (587+623)/2 = 605, try allocation with max pages 605

Try allocation with max_pages=605

Why: Test if 605 is valid max pages limit

Step 15: Allocate books: Student 1 gets 100+200+300=600 (<=605), Student 2 gets 400 (<=605)

Allocation possible with max_pages=605

Why: 605 works, try smaller max

Step 16: Set high = mid - 1 = 604, binary search continues

low=587, high=604

Why: Try smaller max pages

Step 17: Check mid = (587+604)/2 = 595, try allocation with max pages 595

Try allocation with max_pages=595

Why: Test if 595 is valid max pages limit

Step 18: Allocate books: Student 1 gets 100+200=300 (<=595), next book 300 would exceed 595, Student 2 gets 300+400=700 (>595) not allowed

Allocation not possible with max_pages=595

Why: 595 too small

Step 19: Set low = mid + 1 = 596, binary search continues

low=596, high=604

Why: Increase max pages

Step 20: Check mid = (596+604)/2 = 600, try allocation with max pages 600

Try allocation with max_pages=600

Why: Test if 600 is valid max pages limit

Step 21: Allocate books: Student 1 gets 100+200+300=600 (<=600), Student 2 gets 400 (<=600)

Allocation possible with max_pages=600

Why: 600 works, try smaller max

Step 22: Set high = mid - 1 = 599, binary search continues

low=596, high=599

Why: Try smaller max pages

Step 23: Check mid = (596+599)/2 = 597, try allocation with max pages 597

Try allocation with max_pages=597

Why: Test if 597 is valid max pages limit

Step 24: Allocate books: Student 1 gets 100+200=300 (<=597), next book 300 would exceed 597, Student 2 gets 300+400=700 (>597) not allowed

Allocation not possible with max_pages=597

Why: 597 too small

Step 25: Set low = mid + 1 = 598, binary search continues

low=598, high=599

Why: Increase max pages

Step 26: Check mid = (598+599)/2 = 598, try allocation with max pages 598

Try allocation with max_pages=598

Why: Test if 598 is valid max pages limit

Step 27: Allocate books: Student 1 gets 100+200=300 (<=598), next book 300 would exceed 598, Student 2 gets 300+400=700 (>598) not allowed

Allocation not possible with max_pages=598

Why: 598 too small

Step 28: Set low = mid + 1 = 599, binary search continues

low=599, high=599

Why: Increase max pages

Step 29: Check mid = (599+599)/2 = 599, try allocation with max pages 599

Try allocation with max_pages=599

Why: Test if 599 is valid max pages limit

Step 30: Allocate books: Student 1 gets 100+200=300 (<=599), next book 300 would exceed 599, Student 2 gets 300+400=700 (>599) not allowed

Allocation not possible with max_pages=599

Why: 599 too small

Step 31: Set low = mid + 1 = 600, now low > high, binary search ends

low=600, high=599

Why: Search space exhausted, minimum max pages found

Result:

Final allocation max pages = 600
Books allocation:
Student 1: 100 -> 200 -> 300 -> null
Student 2: 400 -> null

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Books []int

func canAllocate(books Books, students int, maxPages int) bool {
	count := 1
	currentSum := 0
	for _, pages := range books {
		if pages > maxPages {
			return false // single book exceeds maxPages
		}
		if currentSum+pages > maxPages {
			count++ // allocate to next student
			currentSum = pages
			if count > students {
				return false // need more students than available
			}
		} else {
			currentSum += pages
		}
	}
	return true
}

func allocateMinimumPages(books Books, students int) int {
	low := 0
	high := 0
	for _, pages := range books {
		if pages > low {
			low = pages // max single book pages
		}
		high += pages // sum of all pages
	}
	result := high
	for low <= high {
		mid := (low + high) / 2
		if canAllocate(books, students, mid) {
			result = mid
			high = mid - 1 // try smaller max pages
		} else {
			low = mid + 1 // increase max pages
		}
	}
	return result
}

func main() {
	books := Books{100, 200, 300, 400}
	students := 2
	minPages := allocateMinimumPages(books, students)
	fmt.Printf("Minimum maximum pages allocated: %d\n", minPages)
}

if pages > maxPages { return false }

Check if a single book exceeds current max pages limit

if currentSum+pages > maxPages { count++; currentSum = pages; if count > students { return false } } else { currentSum += pages }

Allocate books to students without exceeding max pages; move to next student if needed

for _, pages := range books { if pages > low { low = pages }; high += pages }

Initialize binary search bounds: low=max single book, high=sum all pages

mid := (low + high) / 2

Calculate mid as candidate max pages

if canAllocate(books, students, mid) { result = mid; high = mid - 1 } else { low = mid + 1 }

Adjust binary search bounds based on feasibility

Output

Minimum maximum pages allocated: 600

Complexity Analysis

Time: O(n log m) where n is number of books and m is sum of pages; binary search runs log m times and allocation check runs O(n)

Space: O(n) for storing books array

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

Edge Cases

Only one student

All books must be allocated to one student, so max pages is sum of all books

DSA Go

if count > students { return false }

Number of students equals number of books

Each student gets exactly one book, so max pages is max single book pages

DSA Go

if pages > maxPages { return false }

A book has more pages than any guessed max pages

Allocation fails immediately because no student can read that book within max pages

DSA Go

if pages > maxPages { return false }

When to Use This Pattern

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

Common Mistakes

Mistake: Setting low to 0 instead of max book pages, causing invalid guesses
Fix: Initialize low to max pages of a single book to ensure valid search space

Mistake: Not checking if a single book exceeds max pages in feasibility function
Fix: Add check to return false if any book pages > maxPages

Mistake: Incrementing student count incorrectly or forgetting to reset current sum
Fix: Increment student count only when current sum + pages exceeds maxPages and reset current sum to current book pages

Summary

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

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

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