Searching the answer, not the array

Some problems hand you no sorted array at all. They ask for the smallest speed, the largest capacity, the shortest deadline that still works — a number that appears nowhere in the input and cannot be looked up. The candidates for that number are still ordered, and if you can test one cheaply, you can binary search them.

The move has a name — binary search on the answer — and a tell you can read off the constraints before you have any idea how to solve the problem.

The tell in the constraints

A value bound around 10⁹ next to a small n is the signature:

1 <= len(pallets) <= 10^4
1 <= pallets[i] <= 10^9
len(pallets) <= hours <= 10^9

Nothing can be done 10⁹ times, so the answer is not found by enumeration. But 10⁴ items can be swept about thirty times without noticing: 30 × 10⁴ = 3 × 10⁵ operations. The gap between "the answer's range is huge" and "one test over the input is cheap" is precisely the gap binary search closes, and reading the constraint before having an idea is what puts you onto it.

The brute force makes the same point from the other side. Try every rate from 1 upward and stop at the first that fits: correct, and 10⁹ rates × 10⁴ pallets = 10¹³ operations, roughly three hours of arithmetic at 10⁹ operations a second. The waste is that testing rate 500,000,001 after rate 500,000,000 tells you almost nothing new — each test rules out one candidate when it could rule out half.

Five questions before any code

1 · What is the answer? Name it with units. "The packing rate, in cartons per hour." Not "an index into the pallets" — the answer is usually not an element of the input, and confusing the two is the reason people go looking for a sort that does not help.

2 · What are its bounds? lo is the smallest value the check can legally be run at; hi is a value you can prove works. Rate 0 packs nothing and divides by zero, so lo = 1. The largest pallet is a safe hi: at that rate every pallet clears inside its own hour, and the constraint that there are at least as many hours as pallets makes that enough. A loose hi costs one probe; a wrong one costs the answer. If no candidate is guaranteed to work, extend the range by one and use the extra slot as a sentinel.

3 · What is the check? A function feasible(x) -> bool computed directly from the input. Here: sum the hours each pallet needs at rate x and compare with the shift.

4 · Is the check monotone? One sentence, and it must name a direction. Raising r never increases ceil(cartons / r) for any pallet, so the total hours are non-increasing in r, so once a rate fits, every larger rate fits. Without this sentence the technique is not legal and will fail silently.

5 · What does the check cost? One pass, O(n). Multiply it out: O(check × log range). With an O(n) check, n = 10⁴ and a range of 10⁹, that is 30 × 10⁴ = 3 × 10⁵ — about 3 × 10⁷ times less work than the brute force.

Binary search on the answer: a range of candidate values, a feasibility check at its midpoint, and the half of the range each outcome discards100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

The worked search

Take pallets = [3, 6, 7, 11] and hours = 8. A pallet of c cartons at rate r takes ceil(c / r) hours, because a worker only ever draws from one pallet within an hour and the leftover capacity is lost.

from math import ceil

def hours_needed(pallets, r):
    return sum(ceil(c / r) for c in pallets)   # or (c + r - 1) // r

def slowest_rate(pallets, hours):
    lo, hi = 1, max(pallets)                   # hi always works
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(pallets, mid) <= hours:
            hi = mid
        else:
            lo = mid + 1
    return lo

lo = 1, hi = 11. The four probes:

mid	hours at that rate	fits in 8?	after
6	1 + 1 + 2 + 2 = 6	yes	hi = 6
3	1 + 2 + 3 + 4 = 10	no	lo = 4
5	1 + 2 + 2 + 3 = 8	yes	hi = 5
4	1 + 2 + 2 + 3 = 8	yes	hi = 4

The answer is 4, and rate 3 needing ten hours is why it is not 3. Four probes because the range holds 11 candidates and 2⁴ = 16 ≥ 11; at the full constraint of 10⁹ it would be thirty. That search is exactly Overnight restock — work the problem before reading its solution.

Two bounds that look right and are not

hi = sum(pallets) // hours is the tempting upper bound: total work divided by available time. It is wrong here, because the rule that a worker cannot combine two pallets in one hour means the total is not the binding constraint. On [3, 6, 7, 11] with hours = 8 it gives 3, and 3 needs ten hours. Whenever the check has a rounding or packing rule inside it, derive the bound from that rule, not from the totals.

lo = 0 is the other one, and it hides. The first probe is the midpoint, not lo, so the worked input above still probes 5, 2, 4, 3 and returns 4. Rate 0 is reached only once the interval narrows to [0, 1], which needs rate 1 to be feasible — hours = 30 on the same pallets raises ZeroDivisionError on the fourth probe. A latent bug that fires only when the answer is 0 or 1 survives most test suites, which is worse than crashing on the first probe. lo must be a value at which the check is defined, not merely a value below the answer.

When the answer is a real number

If the answer is a float — the smallest radius, the minimum average — the loop has no integers to collapse onto and lo < hi never becomes false. Run a fixed number of iterations instead:

lo, hi = 0.0, 1e9
for _ in range(60):
    mid = (lo + hi) / 2
    if feasible(mid):
        hi = mid
    else:
        lo = mid
return lo

Sixty halvings of a width-10⁹ interval leave 10⁹ / 2⁶⁰ ≈ 8.7 × 10⁻¹⁰ on paper, and that is what you get for a root near the bottom of the range. Near the top float64 stops the bisection first: consecutive doubles just below 2³⁰ are 2²⁹ × 2⁻⁵² ≈ 1.2 × 10⁻⁷ apart, so for a root near 10⁹ the interval bottoms out at that width after about 53 passes and the last seven do nothing. The precision is relative — one part in 2⁵² of the magnitude — so claim ~10⁻⁷ at the top of a 10⁹ range, still inside a 10⁻⁶ tolerance and still no float comparison to reason about. A fixed count also makes the runtime constant and obvious: sixty checks, not "however many the epsilon needs".

In an interview

Answer the five questions out loud, in order, before touching the keyboard: "The answer is the rate, from 1 to the largest pallet. The check is total hours at that rate, one pass, O(n). It is monotone because packing faster never takes longer. So about thirty probes at 10⁴ each, 3 × 10⁵ operations against 10¹³ for the scan."

That is the entire solution as an argument, and it is worth more than the loop — the loop is a template you have already learned.

The mistake that loses points: searching the input when the answer is not in it. Candidates who see an array reach for sorting it, and then cannot explain what sorted order buys them, because the pallets' order was never the difficulty. The question that redirects you is "what number am I choosing?" If the answer is not an element of the input, the input is not the search space.

The second mistake is a slow check. If feasible sorts internally it is O(n log n) per probe and the log factors multiply; sort once outside the loop and the check drops back to O(n).

Check yourself

Constraints say n <= 2 × 10^5 and values up to 10⁹, with a one-second limit. What do you search, and what can each check afford to cost?

Search the value range, not the array: about 30 probes. A one-second budget is roughly 10⁸ simple operations, so 10⁸ / 30 ≈ 3 × 10⁶ per check — an O(n) pass at 2 × 10⁵ fits with a factor of ten to spare, while an O(n log n) check at 3.5 × 10⁶ per probe is already past that budget, and 1.1 × 10⁸ over thirty probes.

The answer is a real number in [0, 10^9] and must be accurate to 10⁻⁶. How many iterations, and how do you write the loop?

The interval must shrink by a factor of 10⁹ / 10⁻⁶ = 10¹⁵, and log₂(10¹⁵) ≈ 50. Run a fixed 60 iterations with for _ in range(60) rather than testing hi - lo > 1e-6, which trades a guaranteed runtime for a float comparison you have to think about.

Your feasibility check needs the input sorted. Where does the sort go, and what does each choice cost?

Outside the loop, once: O(n log n) up front, then O(n) per probe, giving O(n log n + n log range). Sorting inside the check costs O(n log n) on every one of the thirty probes — the same work repeated thirty times for no new information.