Mastering Binary Search on Answer: The Book Allocation Problem

Partners DSA — Mon, 06 Apr 2026 19:50:52 +0000

If you've ever prepared for a technical interview at companies like Google, Amazon, or Adobe, you've likely encountered the "Allocate Books" problem. It is a classic challenge that tests your ability to look beyond traditional binary search and apply it to a range of possible answers.

In this post, we’ll break down the problem and walk through an efficient Java solution that uses the Binary Search on Answer technique.

The Problem Statement

You are given an array of integers arr, where arr[i] represents the number of pages in the i^th book. There are k students. The task is to allocate all books to the students such that:

Each student gets at least one book.
Each student is assigned a contiguous sequence of books.
The maximum number of pages assigned to a student is minimized.

Example

Input: arr = [12, 34, 67, 90], k = 2

Output: 113

Explanation: - Option 1: [12] and [34, 67, 90] → Max = 191

Option 2: [12, 34] and [67, 90] → Max = 157
Option 3: [12, 34, 67] and [90] → Max = 113 The smallest possible maximum is 113.

The Intuition: Binary Search on Answer

Usually, we use Binary Search to find an element in a sorted array. Here, we use it to find a value in a range.

1. Defining the Range

Lower Bound (low): The maximum element in the array. Why? Because a student must be able to carry at least the largest book.
Upper Bound (high): The sum of all elements. This is the case where only 1 student is assigned all the books.

2. The Strategy

We pick a "limit" (the middle of our range). We check: "Is it possible to allocate these books so that no student has more than mid pages?"

If Yes, it might be our answer, but we try to find an even smaller maximum (high = mid - 1).
If No, our limit is too small, so we increase it (low = mid + 1).

The Solution (Java)

Here is a clean implementation of the logic:

class Solution {
    public int findPages(int[] arr, int k) {
        // If students are more than books, it's impossible
        if (arr.length < k) {
            return -1;
        }
        return findSmallestPossibleMaximum(arr, k);
    }

    public int findSmallestPossibleMaximum(int[] arr, int k) {
        int low = 0;
        int high = 0;

        // Step 1: Define search space
        for (int num : arr) {
            high += num;
            low = Math.max(low, num);
        }

        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2; // Avoid potential overflow

            // Step 2: Check feasibility
            if (findNoOfStudents(arr, mid) <= k) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    // Helper function to count students required for a given page limit
    public int findNoOfStudents(int[] arr, int maxPagesAllowed) {
        int student = 1;
        int currentPagesSum = 0;

        for (int i = 0; i < arr.length; i++) {
            if (currentPagesSum + arr[i] > maxPagesAllowed) {
                student++;
                currentPagesSum = arr[i];
            } else {
                currentPagesSum += arr[i];
            }
        }
        return student;
    }
}

Complexity Analysis: Allocate Books

When presenting the Book Allocation problem in an interview or a tutorial, the code is only half the battle. You must be able to explain why the Binary Search on Answer approach is the most efficient.

Time Complexity (TC)

The total time complexity of this solution is:

$O(Nlog(Sum - Max))

Breakdown:

Binary Search Space (O(log(Range))): We are searching for the answer within the range [Max Element, Sum of all Elements]. The number of steps in a binary search is logarithmic relative to the size of the search space.
- Let R = Sum - Max.
- The binary search takes log(R) iterations.
Feasibility Check (O(N)): In every iteration of the binary search, we call the findNoOfStudents (or isPossible) function. This function iterates through the entire array of N books exactly once to determine if the current mid value is a valid page limit.
Total TC: Multiplying the search steps by the work done in each step gives us:

O(Nlog(Sum - Max))

Note: For typical constraints (N = 10^5, Sum = 10^9), log(10^9) is roughly 30. So the total operations are approximately 30 times 10^5, which easily fits within a 1-second time limit.

Space Complexity (SC)

The space complexity of this solution is:

O(1)

Breakdown:

No Auxiliary Data Structures: We do not use any HashMaps, Stacks, or Heaps to solve the problem. We only store a few primitive integer variables (low, high, mid, studentCount, currentPagesSum).
In-Place Processing: We only read from the input array without modifying it or creating a copy.
Iterative Approach: Since we use a while loop for the binary search rather than recursion, there is no extra overhead on the function call stack.

DEV Community: Partners DSA

Mastering Binary Search on Answer: The Book Allocation Problem

The Problem Statement

Example

The Intuition: Binary Search on Answer

1. Defining the Range

2. The Strategy

The Solution (Java)

Complexity Analysis: Allocate Books

Time Complexity (TC)

Breakdown:

Space Complexity (SC)

Breakdown: