Allocate Minimum Pages Binary Search on Answer in DSA Typescript - Time & Space Complexity

Time Complexity: Allocate Minimum Pages Binary Search on Answer

O(n x log m)

Understanding Time Complexity

We want to find how fast the binary search approach works to allocate minimum pages among students.

How does the number of operations grow as the number of books or pages increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function isPossible(books: number[], students: number, maxPages: number): boolean {
  let requiredStudents = 1;
  let currentSum = 0;
  for (const pages of books) {
    if (pages > maxPages) return false;
    if (currentSum + pages > maxPages) {
      requiredStudents++;
      currentSum = pages;
      if (requiredStudents > students) return false;
    } else {
      currentSum += pages;
    }
  }
  return true;
}

function allocateMinimumPages(books: number[], students: number): number {
  let start = Math.max(...books);
  let end = books.reduce((a, b) => a + b, 0);
  let result = end;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (isPossible(books, students, mid)) {
      result = mid;
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return result;
}
    

This code uses binary search on the answer range to find the minimum maximum pages allocated to any student.

Identify Repeating Operations

Look at the loops and checks that repeat.

• Primary operation: The for-loop inside isPossible that checks if allocation is possible.
• How many times: This loop runs once for each book, so n times per check.
• Binary search loop: The while loop in allocateMinimumPages runs about log(sum of pages) times.

How Execution Grows With Input

Each binary search step checks all books once.

Input Size (n)	Approx. Operations
10 books	10 x log(total pages)
100 books	100 x log(total pages)
1000 books	1000 x log(total pages)

As books increase, operations grow linearly with n, multiplied by the logarithm of total pages.

Final Time Complexity

Time Complexity: O(n x log m)

This means the time grows linearly with the number of books and logarithmically with the sum of all pages.

Common Mistake

[X] Wrong: "The binary search alone makes this O(log n) time."

[OK] Correct: Each binary search step runs a full check over all books, so the total time depends on both the number of books and the binary search steps.

Interview Connect

Understanding this time complexity helps you explain how binary search can be used on answers, a common pattern in allocation and partition problems.

Self-Check

What if we used a linear search instead of binary search on the answer range? How would the time complexity change?