L15 · Binary Search III — On the Answer

Series: LeetCode — From Basics to Interview-Ready · Session 15 / 65 · Phase 1 · Core patterns

Watch first

What this pattern IS

So far binary search located something inside an array. The most powerful use flips it: you binary search the answer itself.

Look at questions like: "what's the slowest eating speed Koko can use and still finish the bananas in H hours?" or "what's the smallest ship capacity that delivers all packages within D days?" or "split the array into m parts minimising the largest part sum." There's no array to search — the answer is a number somewhere in a known range (e.g. speed from 1 to max-pile).

The trick: define a boolean feasibility predicate feasible(x) = "can we achieve the goal if the answer is x?" For these problems the predicate is monotone: if a speed of x works, any faster speed also works; if a capacity of x works, any bigger capacity works. So feasible looks like False, False, ..., False, True, True, ..., True over the answer range — exactly the shape L13's template hunts. Binary search finds the boundary: the smallest x that's feasible.

The naive approach tries every candidate x from low to high, each test costing O(n) — that's O(range · n). Binary searching the range makes it O(n · log(range)).

First principles

The templates

Template — binary search the answer for the smallest feasible x

def smallest_feasible(lo, hi, feasible):
    """Smallest x in [lo, hi] with feasible(x) True. feasible must be monotone.
    Assumes at least hi is feasible."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid                # mid works -> maybe smaller does too; keep mid
        else:
            lo = mid + 1            # mid too small -> answer is strictly larger
    return lo                       # smallest feasible value

It is literally L13's template. The entire skill is writing feasible(x) correctly and bounding [lo, hi].

The recipe (memorise the STEPS, not each problem)

# 1. Identify the answer variable and its range [lo, hi].
#    lo = smallest sane value (often max single element or 1)
#    hi = largest sane value (often the sum, or the max pile)
# 2. Write feasible(x): a greedy/simulation check, O(n), returning True/False.
# 3. Confirm monotonicity: bigger x => easier => stays feasible.
# 4. Binary search [lo, hi] with the 'first True' template.

Example feasibility predicate (Koko)

import math
def feasible_koko(piles, h, speed):
    # hours needed at this speed = sum of ceil(pile / speed)
    hours = sum(math.ceil(p / speed) for p in piles)
    return hours <= h            # feasible if it fits in the hour budget

Mental model

Memory / mnemonic

Three letters and a sentence: "BFB — Bound, Feasible, Boundary."

• Bound the answer: what's the smallest and largest x could be? Write lo, hi first.
• Feasible(x): an O(n) yes/no check. Say the sentence "if the answer were x, could I hit the goal?" Code it as a greedy pass.
• Boundary: run L13's exact template on the range. "First True is the answer."

The trigger phrase that should fire this pattern instantly: "minimise the maximum" (or maximise the minimum). Whenever you hear it, reach for BFB. The other tell: the answer is a number in a range, not a position in the input.

The trap

What interviewers actually ask

Binary-search-on-answer is a favourite Amazon/Meta medium because candidates who only know array binary search freeze on it.

• Koko Eating Bananas (875) · Medium · Amazon, Meta — probes: do you spot 'minimise the speed subject to a time budget' as a monotone predicate? Follow-up: what are the correct lo/hi bounds?
• Capacity To Ship Packages Within D Days (1011) · Medium · Amazon — probes: feasible(capacity) via a greedy day-count simulation; lo = max(weight), hi = sum. Follow-up: why lo can't be smaller than the biggest single package.
• Split Array Largest Sum (410) · Hard · Amazon, Google — probes: 'minimise the largest subarray sum over k splits' — the canonical minimise-the-maximum. Follow-up: the DP alternative and why binary search is simpler.
• Minimum Number of Days to Make m Bouquets (1482) · Medium · Amazon — probes: feasible(day) with a scan for consecutive bloomed flowers. Follow-up: impossible-case detection (m*k > n).
• Find the Smallest Divisor Given a Threshold (1283) · Medium · Amazon — probes: feasible(divisor) via sum of ceilings ≤ threshold. Follow-up: identical structure to Koko — can you see it?
• Sqrt(x) (69) · Easy · Amazon — probes: largest m with m*m ≤ x — search-on-answer in its simplest form. Follow-up: extend to real-valued precision.

Universal probe: "there's no array to search — what are you binary searching over, and why is it monotone?" Name the answer range and the monotonicity.

Worked solutions

1. Koko Eating Bananas (875)

Plain words: piles of bananas and H hours. Each hour Koko eats up to speed bananas from one pile (a partial pile still uses a full hour). Find the minimum integer speed to finish all piles within H hours.

Brute force: try every speed from 1 upward until one fits — O(max_pile · n). Insight: feasible(speed) = "hours needed ≤ H" is monotone (faster is never worse), so binary search speed in [1, max(piles)].

import math
def minEatingSpeed(piles, h):
    def hours_at(speed):
        return sum(math.ceil(p / speed) for p in piles)   # O(n)
    lo, hi = 1, max(piles)          # slowest possible = 1, fastest useful = biggest pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if hours_at(mid) <= h:      # feasible -> maybe even slower works
            hi = mid
        else:
            lo = mid + 1            # too slow -> need faster
    return lo

Complexity: O(n · log(max_pile)) time, O(1) memory. Follow-up — "why hi = max(piles)?": at that speed every pile takes exactly one hour, the fewest possible; going faster never reduces the hour count further.

import math
def smallestDivisor(nums, threshold):
    def total(d):
        return sum(math.ceil(x / d) for x in nums)
    lo, hi = 1, max(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if total(mid) <= threshold:
            hi = mid
        else:
            lo = mid + 1
    return lo

2. Capacity To Ship Packages Within D Days (1011)

Plain words: package weights must ship in order; each day a ship carries a prefix of the remaining packages up to its capacity. Find the least capacity that ships everything within D days.

Insight: feasible(cap) = greedily pack days and count how many are needed; feasible iff days_needed ≤ D. Monotone (bigger ship never needs more days). Bounds: lo = max(weights) (must fit the heaviest single package in one day), hi = sum(weights) (one giant day).

def shipWithinDays(weights, days):
    def days_needed(cap):
        needed, load = 1, 0
        for w in weights:
            if load + w > cap:      # can't fit -> start a new day
                needed += 1
                load = 0
            load += w
        return needed
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if days_needed(mid) <= days:   # feasible -> try smaller capacity
            hi = mid
        else:
            lo = mid + 1               # infeasible -> need more capacity
    return lo

Complexity: O(n · log(sum)) time, O(1) memory. Follow-up — "why lo = max(weights)?": a capacity below the heaviest package can never load that package on any day, so no capacity smaller than the max is ever feasible.

3. Split Array Largest Sum (410)

Plain words: split the array into k contiguous non-empty subarrays so that the largest subarray sum is as small as possible; return that minimised largest sum.

Insight: this is the archetypal minimise the maximum. feasible(limit) = "can we split into ≤ k parts if no part may exceed limit?" — greedily start a new part whenever adding the next element would exceed limit, count parts. Monotone (a bigger limit never needs more parts). Bounds: lo = max(nums), hi = sum(nums).

def splitArray(nums, k):
    def parts_needed(limit):
        parts, cur = 1, 0
        for x in nums:
            if cur + x > limit:     # exceeds the cap -> open a new part
                parts += 1
                cur = 0
            cur += x
        return parts
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if parts_needed(mid) <= k:  # feasible within k parts -> try a tighter cap
            hi = mid
        else:
            lo = mid + 1            # needs too many parts -> raise the cap
    return lo

Complexity: O(n · log(sum)) time, O(1) memory. Follow-up — "the DP solution": an O(k·n^2) interval DP also works but is slower and harder to code; binary-search-on-answer is the preferred interview answer.

Tradeoff

Where this shows up

Binary-search-on-answer is exactly how many scheduling and provisioning systems size resources: "what's the smallest number of machines (or the smallest per-worker load) that finishes the batch within the SLA?" is a monotone feasibility test (more machines never miss a deadline that fewer would meet) searched over a capacity range. Rate limiters and autoscalers use the same shape to find the minimal capacity that keeps latency under a threshold, and load balancers use it to compute the minimal max-bin when distributing tasks.

Checkpoint

Quiz

Practice queue

+7d / +21d mark spaced-repetition anchors.

• Sqrt(x) (69) — Easy · simplest search-on-answer.
• Koko Eating Bananas (875) — Medium · the archetype · +7d anchor.
• Find the Smallest Divisor Given a Threshold (1283) — Medium · Koko in disguise.
• Capacity To Ship Packages Within D Days (1011) — Medium · greedy feasibility.
• Minimum Number of Days to Make m Bouquets (1482) — Medium · scan-based predicate.
• Split Array Largest Sum (410) — Hard · minimise the maximum · +21d anchor.
• Minimize Max Distance to Gas Station (774) — Hard · real-valued search-on-answer.