Pattern #11

Binary Search on Answer

Important interview questions, thinking patterns, decision boundaries, and rules for solving binary search on answer problems in Go.

Must Solve

15 core questions — solve these first.

1.Koko Eating Bananas
BS speed range [1..maxPile]medium
2.Capacity To Ship Packages Within D Days
BS capacity range [maxPkg..sumPkg]medium
3.Minimum Number of Days to Make m Bouquets
BS day range [minDay..maxDay]medium
4.Split Array Largest Sum
BS max sum range [maxVal..sumVal]hard
5.Aggressive Cows
BS min distance range [1..maxDist]medium
6.Allocate Minimum Number of Pages
BS max pages range [maxPages..sumPages]medium
7.Magnetic Force Between Two Balls
BS min force range [1..maxDist]medium
8.Minimum Speed to Arrive on Time
BS speed range [1..10^7]medium
9.Minimum Limit of Balls in a Bag
BS penalty size range [1..maxSize]medium
10.Find the Smallest Divisor Given a Threshold
BS divisor range [1..maxVal]medium
11.Maximum Candies Allocated to K Children
BS pile size range [1..maxPile]medium
12.Minimum Time to Complete Trips
BS time range [1..minTime*totalTrips]medium
13.Painter's Partition Problem
BS max time per paintermedium
14.Maximum Running Time of N Computers
BS battery time range [1..sum/n]hard
15.Minimized Maximum of Products Distributed to Any Store
BS max products per storemedium

Also Important

8 more questions worth practicing.

16.Cutting Ribbons
BS ribbon lengthmedium
17.Maximum Value at a Given Index in a Bounded Array
BS target element valuemedium
18.Minimum Capability of a Robber
BS max house value stolenmedium
19.House Robber IV
BS capability thresholdmedium
20.Repair Cars
BS time rangemedium
21.Maximum Number of Removable Characters
BS k removable prefix indexmedium
22.Minimum Time to Repair Cars
BS time to repair all carsmedium
23.Minimum Number of Seconds to Make Mountain Height Zero
BS time for worker height reductionmedium

How to Think

Question asks minimum possible X?Binary Search on Answer
Question asks maximum possible X?Binary Search on Answer
Can test "Is X possible?" (false..false..true..true)?Binary Search the boundary

Go Templates

Minimum Valid Answer Template (e.g. Koko Eating Speed)

left, right := low, high
answer := high

for left <= right {
    mid := left + (right-left)/2
    if can(mid) { // Test candidate
        answer = mid
        right = mid - 1 // Try smaller valid
    } else {
        left = mid + 1  // Need larger candidate
    }
}

Maximum Valid Answer Template (e.g. Max Distance)

left, right := low, high
answer := low

for left <= right {
    mid := left + (right-left)/2
    if can(mid) {
        answer = mid
        left = mid + 1  // Try larger valid
    } else {
        right = mid - 1 // Need smaller candidate
    }
}

Core Pattern & The `can(mid)` Function

The most important part of Binary Search on Answer is creating a helper function can(mid) that returns true or false:

can(mid) → Can speed 'mid' finish in H hours?
can(mid) → Can capacity 'mid' ship in D days?
can(mid) → Can distance 'mid' place K cows?

Binary search handles halving the search range in O(log Range) while can(mid) checks if a candidate works in O(N).

Visual Memory Rule

❌ ❌ ❌ ❌ ✅ ✅ ✅
            ↑
       first valid (Minimum Valid Answer)

Minimum valid  →  can(mid) valid? Save ans → move RIGHT = mid - 1
Maximum valid  →  can(mid) valid? Save ans → move LEFT = mid + 1

💡 Golden Rule: "If you can test 'Can this answer work?' and the result changes only once, binary search the answer."

Common Interview Mistakes

1. Wrong Range Bounds

Setting low/high wrong (e.g. shipping capacity low must be max(packages), not 1).

2. Flawed can(mid) Logic

Most bugs occur inside can(mid) simulation, not the binary search loop.

3. Searching Wrong Direction

For minimum answer: valid → go smaller (right = mid - 1). For max answer: valid → go bigger.

4. Non-Monotonic Condition

Make sure if X works, every bigger/smaller X also works (❌ ❌ ✅ ✅).

Interview Rules

1. Minimum possible value? → Think Binary Search on Answer
2. Maximum possible value? → Think Binary Search on Answer
3. Can test candidate with true/false? → Good sign
4. `false false true true`? → Find first true (min valid)
5. `true true false false`? → Find last true (max valid)
6. Minimum valid → valid means search left (right = mid - 1)
7. Maximum valid → valid means search right (left = mid + 1)
8. Main challenge → write correct can(mid) helper
9. Complexity → O(check × log Range)

Small Rules

Rule 1: You need a monotonic condition (❌ ❌ ❌ ✅ ✅ ✅).
Rule 2: Find good lower and upper bounds (e.g. shipping capacity low = max package, high = sum packages).
Rule 3: Minimum valid: if valid, save ans, right = mid - 1.
Rule 4: Maximum valid: if valid, save ans, left = mid + 1.
Rule 5: Overall complexity is O(n log range) if check is O(n).

Production Thinking

Server Capacity → Minimum server capacity X that handles peak traffic

Batch Processing → Minimum batch size X to complete jobs before deadline

Network Rate → Minimum bandwidth X to transfer payload in SLA window

Resource Allocation → Maximum safe load X per worker node

Remember This

Minimum answer                 → find first valid
Maximum answer                 → find last valid
Candidate works?               → can(mid)
Valid minimum?                 → go left (right = mid - 1)
Valid maximum?                 → go right (left = mid + 1)
Impossible candidate?          → move toward valid side