Mastering Binary Search on Answer: The Book Allocation Problem

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:

1. Each student gets at least one book.
2. Each student is assigned a contiguous sequence of books.
3. 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:

1. 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.

2. 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.

3. 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.

---