Allocate Minimum Number of Pages | Binary Search on Answer

Problem Statement

Given:

• books[i] = pages in ith book
• m students

Allocate books such that:

• Every student gets at least one book.
• Books are allocated contiguously.
• Every book is assigned.

Minimize:

Maximum pages assigned to any student

Enter fullscreen mode Exit fullscreen mode

Return the minimum possible value.

Brute Force Intuition

In an interview, you can explain it like this:

Try every possible maximum page limit and check whether it is possible to distribute books among students while respecting that limit.

This works but is inefficient.

Complexity

• Time Complexity: O(N × Sum)
• Space Complexity: O(1)

Moving Towards the Optimal Approach

Think about the answer.

Minimum possible answer:

Maximum book pages

Enter fullscreen mode Exit fullscreen mode

because one student must take that book.

Maximum possible answer:

Sum of all pages

Enter fullscreen mode Exit fullscreen mode

when one student takes all books.

So answer lies in:

[max(book), sum(book)]

Enter fullscreen mode Exit fullscreen mode

This screams:

Binary Search on Answer

Enter fullscreen mode Exit fullscreen mode

Pattern Recognition

Whenever you see:

• Minimize Maximum
• Maximize Minimum
• Feasibility Check

Think:

Binary Search on Answer

Key Observation

Suppose:

Maximum allowed pages = X

Enter fullscreen mode Exit fullscreen mode

Can we allocate books to at most:

m students

Enter fullscreen mode Exit fullscreen mode

?

If yes:

Try smaller answer

Enter fullscreen mode Exit fullscreen mode

If no:

Need larger answer

Enter fullscreen mode Exit fullscreen mode

Feasibility Function

For every book:

Add pages to current student

Enter fullscreen mode Exit fullscreen mode

If limit exceeded:

Assign new student

Enter fullscreen mode Exit fullscreen mode

Count students required.

Optimal Java Solution

class Solution {

    public int findPages(int[] arr,
                         int n,
                         int m) {

        if (m > n)
            return -1;

        int low = 0;
        int high = 0;

        for (int pages : arr) {

            low = Math.max(low, pages);
            high += pages;
        }

        while (low <= high) {

            int mid = low + (high - low) / 2;

            int students =
                countStudents(arr, mid);

            if (students > m) {

                low = mid + 1;

            } else {

                high = mid - 1;
            }
        }

        return low;
    }

    private int countStudents(int[] arr,
                              int maxPages) {

        int students = 1;
        int pages = 0;

        for (int book : arr) {

            if (pages + book <= maxPages) {

                pages += book;

            } else {

                students++;
                pages = book;
            }
        }

        return students;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

books = [12,34,67,90]

students = 2

Enter fullscreen mode Exit fullscreen mode

Search Space:

low = 90
high = 203

Enter fullscreen mode Exit fullscreen mode

Iteration 1

mid = 146

Enter fullscreen mode Exit fullscreen mode

Allocation:

12 + 34 + 67 = 113

Next 90 exceeds

Enter fullscreen mode Exit fullscreen mode

Student 2 gets:

90

Enter fullscreen mode Exit fullscreen mode

Students Needed:

2

Enter fullscreen mode Exit fullscreen mode

Valid.

Try smaller answer.

Iteration 2

mid = 117

Enter fullscreen mode Exit fullscreen mode

Students Needed:

2

Enter fullscreen mode Exit fullscreen mode

Still valid.

Try smaller.

Eventually:

113

Enter fullscreen mode Exit fullscreen mode

becomes answer.

Why Binary Search Works?

If:

113 pages works

Enter fullscreen mode Exit fullscreen mode

Then:

114
115
116
...

Enter fullscreen mode Exit fullscreen mode

will also work.

This monotonic behaviour allows Binary Search.

Complexity Analysis

Metric Complexity Time Complexity O(N × log(Sum)) Space Complexity O(1)

Interview One-Liner

Binary search the maximum pages a student can receive and check if allocation is possible within m students.

Pattern Learned

Minimize Maximum
+
Feasibility Check

=> Binary Search on Answer

Enter fullscreen mode Exit fullscreen mode

Similar Problems

• Allocate Minimum Pages
• Aggressive Cows
• Painter’s Partition
• Capacity To Ship Packages
• Koko Eating Bananas
• Minimum Days To Make Bouquets

Memory Trick

Think:

Can all books be allocated
if no student gets
more than X pages?

Enter fullscreen mode Exit fullscreen mode

YES
→ Try Smaller

NO
→ Increase X

Enter fullscreen mode Exit fullscreen mode

Mental Model

Answer Exists in Range
        ↓
Check Feasibility
        ↓
Binary Search

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Minimize the maximum”

your brain should immediately think:

Binary Search on Answer 🚀