Allocate Minimum Pages Binary Search on Answer in DSA Typescript - Execution Trace

Concept Flow - Allocate Minimum Pages Binary Search on Answer

Set low = max(pages array)

↓

Set high = sum(pages array)

↓

While low <= high

↓

Calculate mid = Math.floor((low + high) / 2)

↓

Check if allocation possible with mid

↓

Update high = mid-1

↓

Repeat loop

↓

Return low as minimum max pages

We use binary search on the range of possible max pages to find the minimum max pages per student that allows allocation.

Execution Sample

DSA Typescript

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

This function checks if pages can be allocated to students such that no student gets more than mid pages.

Execution Table

Step	Operation	low	high	mid	Allocation Possible?	Action	Visual State (Allocation)
1	Initialize low and high	max pages = 40	sum pages = 110	-	-	-	Pages: [10,20,30,40,10]
2	Calculate mid	40	110	75	-	-	-
3	Check allocation with mid=75	-	-	75	Yes	high = mid - 1 = 74	Allocations: [10+20+30=60], [40], [10] (3 students)
4	Calculate mid	40	74	57	-	-	-
5	Check allocation with mid=57	-	-	57	Yes	high = mid - 1 = 56	Allocations: [10+20=30], [30], [40+10=50] (3 students)
6	Calculate mid	40	56	48	-	-	-
7	Check allocation with mid=48	-	-	48	No	low = mid + 1 = 49	Allocations fail: [10+20=30], [30], [40+10=50 > 48]
8	Calculate mid	49	56	52	-	-	-
9	Check allocation with mid=52	-	-	52	Yes	high = mid - 1 = 51	Allocations: [10+20=30], [30], [40+10=50]
10	Calculate mid	49	51	50	-	-	-
11	Check allocation with mid=50	-	-	50	Yes	high = mid - 1 = 49	Allocations: [10+20=30], [30], [40+10=50]
12	Calculate mid	49	49	49	-	-	-
13	Check allocation with mid=49	-	-	49	No	low = mid + 1 = 50	Allocations fail: [10+20=30], [30], [40+10=50 > 49]
14	Loop ends	50	49	-	-	-	low > high, stop
15	Return result	-	-	-	-	Return low = 50	-

💡 Loop ends when low (50) > high (49), minimum max pages per student is 50.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	Final
low	40	40	40	49	49	49	50	50
high	110	74	56	56	51	49	49	49
mid	-	75	57	48	52	50	49	-
Allocation Possible?	-	Yes	Yes	No	Yes	Yes	No	-

Key Moments - 3 Insights

Why do we set low to the maximum pages in the array at the start?

Because no student can be allocated less than the largest single book's pages, so low starts at max pages (Step 1 in execution_table).

Why do we update high to mid - 1 when allocation is possible?

Because if allocation is possible with mid, we try to find a smaller max by reducing high (see Steps 3, 5, 9, 11).

Why do we update low to mid + 1 when allocation is not possible?

Because mid is too small to allocate pages properly, so we increase low to search higher (see Steps 7, 13).

Visual Quiz - 3 Questions

Look at the execution_table at Step 7, what is the value of low after this step?

A 49

B 48

C 50

D 47

💡 Hint

Check the 'Action' column at Step 7 where low is updated to mid + 1 = 49.

At which step does the allocation become impossible for the first time?

A Step 3

B Step 7

C Step 5

D Step 9

💡 Hint

Look at the 'Allocation Possible?' column to find the first 'No' value.

If the number of students increased, how would the final minimum max pages change?

A It would stay the same

B It would increase

C It would decrease

D It would become zero

💡 Hint

More students means pages can be split more, so max pages per student decreases.

Concept Snapshot

Allocate Minimum Pages using Binary Search:
- Set low = max pages in array
- Set high = sum of all pages
- While low <= high:
  - mid = Math.floor((low + high) / 2)
  - Check if allocation possible with mid
  - If yes, high = mid - 1
  - Else, low = mid + 1
- Return low as minimum max pages

Full Transcript

This concept uses binary search on the answer space to allocate minimum pages to students. We start low at the largest single book pages and high at the total pages. We calculate mid and check if allocation is possible without exceeding mid pages per student. If possible, we try smaller mid by moving high down. If not, we increase low. We repeat until low passes high. The final low is the minimum maximum pages per student. The execution table shows each step's low, high, mid, allocation check, and actions. Variable tracker shows how low, high, mid, and allocation results change. Key moments clarify why low starts at max pages, why high moves down on success, and low moves up on failure. The quiz tests understanding of these steps and effects of changing students.