DSA sheet · Binary Search · Binary search on answer (min of max)

Allocate Minimum Pages

Books sit in a row, and we must hand them out to k students in continuous blocks. The student with the most pages has the hardest job, and we want that hardest job to be as light as possible. This is the "minimise the maximum" version of binary search on the answer, the mirror image of Aggressive Cows. The teacher first lists every possible split by hand to understand the question, then picks the answer range (max book → total pages), writes a "how many students do I need?" check, runs the brute force to show the TLE, and finally binary searches over the range.

Why it matters: this problem is the parent of a whole family (Split Array Largest Sum, Painter's Partition, Ship Packages). Split Array Largest Sum is literally the same code.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: try every page limit one by one
• Part B · Optimal: binary search on the page limit
• Part C · Revision page

Part 0 · Before starting

Normal binary search in one paragraph

Binary search works when a yes/no question changes its answer only once along a sorted line. Keep low and high, test the middle mid, and throw away the half that can't hold the answer. Each step halves the range, so about log₂(size) steps are needed.

How to compute mid, and why that form

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

The value is the same as (low + high) // 2. In Java or C++, adding two big ints can go past the int limit (about 2.1 × 10⁹) and give a wrong negative number. high - low never overflows. The teacher says she uses this form whenever the constraints are big. Here high is a sum of pages, which can reach 10⁶ × 10³ = 10⁹. Python integers never overflow, so in Python it's only a good habit.

The pattern: binary search on the answer

1. Answer range: the smallest possible answer (low) and the largest (high).
2. Yes/no check: test one candidate. Here: "if no student may read more than X pages, can k students cover all the books?"
3. Monotonic: all the noes on one side, all the yeses on the other. Then binary search finds the boundary.

The teacher's tell-tale sign: in the example the answer is 113, and 113 is not in the array. The answer doesn't come from the input array, it comes from a range of numbers. That's why we binary search a range and not the array. (The example array happens to be sorted, but that doesn't help us. She asks whether to binary search the array itself and says no.)

Minimise the maximum vs maximise the minimum

Part A · Brute force: try every page limit one by one

GeeksforGeeks · Allocate Minimum Pages

1The question in simple words

arr[i] is the number of pages in book i. There are k students. Hand out all the books so that:

• every student gets at least one book,
• each student gets a continuous run of books (like books 2, 3, 4, never books 1 and 3 without 2),
• no book is split or shared between two students.

For each way of handing out, look at the student with the most pages. Among all ways, pick the one where that number is smallest, and return it. If it can't be done (more students than books), return −1.

Example: arr = [12, 34, 67, 90], k = 2 → answer 113.

2What the constraints tell us

• n (number of books) up to 10⁶. One pass over the books is 10⁶ steps, so we can afford it a few dozen times, not thousands of times.
• arr[i] from 1 to 10³. So the total pages are at most 10⁶ × 10³ = 10⁹. That fits in an int, but it's large.
• k from 1 to 10³. k can be 1, meaning one student gets everything. k can also be bigger than n, and then some student would get no book → answer −1.
• More than about 10⁸ steps → TLE.

3Intuition

Listing every way to cut the row works only for tiny inputs. Instead, fix a limit X and ask: "if nobody may read more than X pages, how many students do I need?" Fill the first student's pile book by book until the next book would cross X, then start a new student. Count the students.

• If we need more than k students, X is too small.
• If k or fewer are enough, X is possible.

Try X = low, low + 1, …. The first X that is possible is the smallest maximum, which is our answer.

4Building the logic from examples

Step 1: list every split for k = 2 (the teacher's first step)

For each split we take the maximum (the busiest student). Then over all splits we take the minimum of those. min(191, 157, 113) = 113. "Minimise the maximum" in one table.

Step 2: the highest possible answer (high)

The teacher looks at the smallest k the constraints allow, k = 1. One student must take every book, so the answer is the whole sum, 12 + 34 + 67 + 90 = 203. With more students the load is shared and the answer can only go down. So no answer is ever above the total. high = sum(arr).

Step 3: the lowest possible answer (low)

She first says the answer lies somewhere from 1 to 203, then tightens it to start at 90, the biggest book. She leaves "why the max and not the min (12)?" as homework. Here's the answer:

So the answer lives on the line 90 … 203.

Step 4: the check with limit 90

• 12 → pile 12. Add 34 → 46 ≤ 90, keep.
• Add 67 → 113 > 90 ✗. Close this pile. A new student starts with 67.
• Add 90 → 157 > 90 ✗. A new student starts with 90.
• Piles: [12, 34] [67] [90] → 3 students needed, but we only have 2 → no.

Should we go higher or lower? With 90 we needed too many students. A bigger limit lets more books share a pile, so fewer students are needed. Go higher.

Step 5: the check with limit 150

12 + 34 + 67 = 113 ≤ 150. Adding 90 → 203 > 150, so a new pile starts with 90. Piles: [12, 34, 67] [90] → 2 students → yes. Now we'd like to see if something smaller (149, 148, …) still works. Go lower.

The yes/no line

The check function, piece by piece

• students = 1, pages_sum = 0: the first student is already open.
• For each book: if pages_sum + pages <= limit, the book joins the current pile.
• Else: open a new student (students += 1) and start that pile with this book: pages_sum = pages.
• At the end: students <= k → yes.

5Approach steps

1. If k > n → return −1.
2. low = max(arr), high = sum(arr).
3. For limit = low … high: if the check says yes → return limit (the first yes is the smallest).
4. (Unreachable, but kept from the teacher's code) return −1.

6Code (Python)

class Solution:
    def findPages(self, arr, k):
        if k > len(arr):                 # more students than books
            return -1
        low = max(arr)                   # the biggest book must fit somewhere
        high = sum(arr)                  # one student reads everything
        for limit in range(low, high + 1):
            if self.isPossible(arr, k, limit):
                return limit             # first yes = smallest maximum
        return -1

    def isPossible(self, arr, k, limit):
        students = 1
        pages_sum = 0
        for pages in arr:
            if pages_sum + pages <= limit:
                pages_sum += pages       # same student takes this book
            else:
                students += 1            # new student...
                pages_sum = pages        # ...starting with THIS book
        return students <= k

7Code line by line

8Dry run (hand table)

arr = [12, 34, 67, 90], k = 2. low = 90, high = 203.

24 checks (90 through 113), each walking all 4 books. Return 113 ✓.

9Complexity & remember

• Time O((sum − max) · n). The teacher counts the outer loop as about 10³ and the inner as 10⁶, so 10⁹ → TLE (and she shows the TLE on submit).
• Space O(1).

The inner walk can't be avoided, since every book has to be placed. But the limits low … high are a sorted number line with one N→Y flip, so the outer loop can be a binary search.

Part B · Optimal: binary search on the page limit

1The question

Same problem. Same low, high and check. The for loop becomes a binary search loop. Nothing else changes, as the teacher says.

2Constraints

Same as Part A. The range has at most about 10⁹ values, so about log₂(10⁹) ≈ 30 checks, each 10⁶ steps.

3Intuition

The line is N N N … Y Y Y and we want the first Y.

• check(mid) yes (≤ k students): mid might be the answer, so save it. But a smaller limit might also work, and we want the minimum → search left: high = mid - 1. (Her example: 150 works, so try 149 and below.)
• check(mid) no (too many students): mid is too small, and so is everything below it → search right: low = mid + 1. (Her example: 90 fails, so look above 90.)

4Building the logic

The range shrinking

5Approach steps

1. If k > n → return −1.
2. low = max(arr), high = sum(arr), answer = high.
3. While low <= high: mid = low + (high - low) // 2.
4. isPossible(mid) → answer = mid, high = mid - 1. Otherwise → low = mid + 1.
5. Return answer.

6Code (Python)

class Solution:
    def findPages(self, arr, k):
        if k > len(arr):
            return -1
        low = max(arr)
        high = sum(arr)
        answer = high
        while low <= high:
            mid = low + (high - low) // 2      # candidate page limit
            if self.isPossible(arr, k, mid):
                answer = mid                   # works: save it...
                high = mid - 1                 # ...and try a smaller limit
            else:
                low = mid + 1                  # too many students: go bigger
        return answer

    def isPossible(self, arr, k, limit):
        students = 1
        pages_sum = 0
        for pages in arr:
            if pages_sum + pages <= limit:
                pages_sum += pages
            else:
                students += 1
                pages_sum = pages
        return students <= k

7Code line by line

8Dry run (hand table)

arr = [12, 34, 67, 90], k = 2.

7 checks instead of the 24 the brute force needed.

9Complexity & remember

• Time O(n · log(sum − max)). The teacher's estimate: log₂(10³) ≈ 10 checks × 10⁶ = 10⁷ → passes. With the full range up to 10⁹, it's log₂(10⁹) ≈ 30 checks × 10⁶ = 3 × 10⁷. Still under 10⁸, so it passes either way.
• Space O(1).

Her tip for picking low and high: at first, find them by trying small cases by hand (k = 1 gave high, the biggest book gave low). After a few problems you start to see them straight away.

Part C · Revision page

s = Solution()
print(s.findPages([12, 34, 67, 90], 2))      # 113
print(s.findPages([15, 17, 20], 5))          # -1
print(s.findPages([22, 23, 67], 1))          # 112
print(s.findPages([15, 10, 19, 10, 5, 18, 7], 5))   # 25

Based on this video: Allocate Minimum Number of Pages | Binary Search on Answer