Lab 04 — Binary Search On Answer: Capacity To Ship Packages Within D Days

Goal

Master the parametric/binary-search-on-answer pattern: identify the monotonic predicate, prove its monotonicity, write a correct feasible(x) independently, then drive a half-open binary search over the answer space. Deliverable solves LC 1011 in O(N · log(sum)) time, O(1) space, and you can articulate the bounds, the predicate’s monotonicity proof, and the canonical [lo, hi) template’s termination.

Background Concepts

Decision problem vs optimization problem; parametric search; monotone predicates; the half-open [lo, hi) invariant feasible(hi-1) = true, feasible(lo-1) = false; greedy verification of feasibility. Review pattern Binary Search On Answer and the constraint→complexity table.

Interview Context

Binary search on answer is the single highest-value pattern for distinguishing strong from elite candidates in 30-minute Mediums. Most candidates can do binary search on a sorted index. Few can recognize that “min capacity such that we can ship in D days” is the same binary search, just over a different domain. Once you internalize this, an entire family of problems collapses: Koko bananas, split-array-largest-sum, smallest divisor, minimum days for bouquets, magnetic force balls, kth-smallest-in-multiplication-table. The pattern is identical; only feasible changes.

Problem Statement

A conveyor belt has packages with weights weights[i]. Each day you load packages in order and ship them on a boat with weight capacity C. Once loaded, the boat ships and starts again the next day. Return the minimum capacity C such that all packages ship within D days.

Constraints

• 1 ≤ D ≤ |weights| ≤ 5 × 10^4
• 1 ≤ weights[i] ≤ 500

Clarifying Questions

1. Must packages be loaded in given order? (Yes — this is the crux. If we could reorder, it becomes a bin-packing problem, which is NP-hard.)
2. Can a package’s weight exceed the daily capacity? (No — capacity must be at least max(weights), else that package never ships.)
3. Can the boat be partially filled and still ship that day? (Yes — when adding the next package would exceed C, you ship the current load and start fresh.)
4. Is D strict (must use all D days) or upper-bound (≤ D days)? (Upper-bound: any number of days ≤ D is acceptable.)
5. Are weights integers, and if so, is the answer always an integer? (Yes and yes.)

Examples

For the first: C=15 ships as [1,2,3,4,5] (15) | [6,7] (13) | [8] (8) | [9] (9) | [10] (10) — 5 days. C=14 would split day 1 into [1,2,3,4] | [5,6,7] | … and need 6+ days.

Initial Brute Force

Try every capacity from max(weights) to sum(weights); for each, simulate and check if D days suffice; return the first that works.

def ship_capacity_brute(weights, D):
    for C in range(max(weights), sum(weights) + 1):
        if feasible(weights, D, C): return C

def feasible(weights, D, C):
    days, load = 1, 0
    for w in weights:
        if load + w > C:
            days += 1; load = 0
        load += w
    return days <= D

Brute Force Complexity

Time O(N · range), where range = sum - max ≈ N · 500. So O(N²·500) ≈ 1.25×10^9. TLEs.

Optimization Path

Key observation: feasibility is monotonic in capacity. If C works (ships in ≤ D days), any C' > C also works (the greedy simulation can only do better — it never has to start a new day earlier). Equivalently, if C doesn’t work, no C' < C works.

So the set {C : feasible(C) == true} is an upward-closed half-line [C*, ∞). We binary search for C*.

Bounds:

• Low: max(weights) — any capacity below this can’t even ship the heaviest package alone.
• High: sum(weights) — capacity ≥ total ships everything in 1 day, trivially ≤ D days.

Final Expected Approach

def ship_capacity(weights, D):
    def feasible(C):
        days, load = 1, 0
        for w in weights:
            if load + w > C:
                days += 1; load = w
            else:
                load += w
            if days > D: return False
        return True

    lo, hi = max(weights), sum(weights) + 1   # half-open [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Note hi = sum + 1 (half-open) and the canonical lo < hi loop condition.

Data Structures Used

None beyond the input array and three integers (lo, hi, mid) plus two more inside feasible.

Correctness Argument

Monotonicity: Let feasible(C) be true. For C' > C, the greedy simulation with capacity C' packs at least as much per day as it would with C (because the “if load + w > C” branch fires at most as often). So days-needed-with-C' ≤ days-needed-with-C ≤ D. Hence feasible(C') is true. The set of feasible C is upward-closed.

Greedy feasibility: the greedy “ship today as much as fits” is optimal for min days given fixed C, by an exchange argument: if there’s a schedule that ships in fewer days, we can shift weight from a later day to an earlier day without exceeding C, monotonically reducing days. So feasible(C) correctly reports whether some schedule fits in D days.

Binary search invariant (half-open [lo, hi)): feasible(lo - 1) = false (or lo - 1 < max(weights)) and feasible(hi) either true or hi = sum + 1 (definitely feasible). The loop preserves this. On termination lo == hi, and feasible(lo) = true, feasible(lo - 1) = false. So lo is the minimum feasible C.

Termination: each iteration strictly shrinks hi - lo by at least 1 (in the mid + 1 branch) or halves it (in the hi = mid branch). Bounded by O(log(hi - lo)).

Complexity

Time O(N · log(sum - max)). With N = 5×10^4 and sum bounded by 2.5×10^7, that’s ~5×10^4 × 25 ≈ 1.25×10^6 ops. Easily sub-100ms in any language. Space O(1) additional.

Implementation Requirements

• Write feasible first, test it independently on the examples, then wrap it in binary search. Many bugs are in feasible, not the search.
• Use hi = sum + 1 half-open, or hi = sum and <=; pick one convention and stick to it. The half-open [lo, hi) template returns lo exactly.
• Early-return from feasible once days > D — saves time on small C.
• Don’t forget that on the “doesn’t fit” branch, the new day starts with the current package as its load, not zero (or else the next package may also overflow).

Tests

• Smoke: the four examples above.
• Unit: D = N (each package its own day) → answer is max(weights). D = 1 → answer is sum(weights).
• Edge: all-equal weights, [5,5,5,5], D=2 → answer 10. Single weight, [42], D=1 → 42.
• Independence test for feasible: for the first example, verify feasible(15)=true, feasible(14)=false, feasible(55)=true, feasible(10)=false.
• Large: N = 5×10⁴, weights random in [1, 500], D = 1000; assert sub-100ms. Cross-check against brute on a 100-element prefix.
• Adversarial: sorted ascending, sorted descending, all-max (weights all 500). The greedy is still optimal regardless of ordering (well, the answer depends on ordering since reorder is forbidden).

Follow-up Questions

• “What if package order is flexible?” → bin packing, NP-hard. Approximation: First-Fit-Decreasing achieves 11/9 OPT.
• “What if D is very large (D ≥ N)?” → answer is max(weights); you can early-return.
• “What if you must use exactly D days?” → still binary-searchable (monotonicity holds for “≤ D days”; for “exactly D”, parametrize differently — but in practice you almost always want ≤ D).
• “What about Koko Eating Bananas (LC 875)?” → identical pattern; feasible(speed) = sum(ceil(p / speed) for p in piles) ≤ H.
• “Split array largest sum (LC 410)?” → identical pattern; feasible(maxSum) = (greedy partition into pieces of sum ≤ maxSum, count ≤ K).
• “Floating-point answer?” → loop until hi - lo < eps, return lo. Watch for non-termination if eps is below float precision.

Product Extension

Capacity planning for a build pipeline: given a stream of CI jobs with known durations and a deadline D, find the minimum machine-count or the minimum machine-capacity that meets the deadline. Same pattern: monotonic in capacity, binary-search on answer with greedy feasibility. Generalizes to load-balancer auto-scaling: minimum number of pods s.t. p99 latency stays below SLA, given a workload trace. (The feasibility check becomes a simulator instead of a one-line greedy, but the structure is identical.)

Language/Runtime Follow-ups

• Python: (lo + hi) // 2 is fine — Python ints are arbitrary precision. No overflow.
• Java: int mid = lo + (hi - lo) / 2; to avoid 32-bit overflow when lo + hi exceeds Integer.MAX_VALUE. (For this problem’s constraints, lo + hi won’t overflow, but build the habit.)
• Go: same overflow caveat as Java; use lo + (hi - lo) / 2.
• C++: same; use lo + (hi - lo) / 2. int may also be too small for sum(weights) if constraints expand — use long long.
• JS/TS: numbers are 64-bit floats, integer-precise up to 2^53. No overflow risk for this problem. But beware: Math.floor((lo + hi) / 2) is slower than (lo + hi) >>> 1 (zero-fill right shift), and the latter is what idiomatic JS binary-search uses.
• Edge: for floating-point binary search (not this problem), terminate by iteration count (e.g., 100 rounds) rather than hi - lo < eps to dodge non-termination near float precision.

Common Bugs

1. Wrong bounds. lo = 1 instead of lo = max(weights) — the search may return a value that doesn’t fit the heaviest package (well, the binary search finds the smallest feasible value; if you start lo too low and feasible is correct, you still get the right answer — but you waste log(max) iterations and the symmetry of the bounds is broken). hi = sum instead of sum + 1 with lo < hi mis-handles the case where the answer is sum.
2. Inverted predicate direction. Searching for “max C such that infeasible” instead of “min C such that feasible” — flips the bounds and breaks the invariant.
3. feasible bug: forgetting to start the new day with the current package. Setting load = 0 instead of load = w after exceeding capacity corrupts the count for runs of large weights.
4. feasible bug: starting days = 0 instead of days = 1. The first day exists before any package ships.
5. Off-by-one in the binary search template. Mixing < with <= and mid with mid - 1 and mid + 1 is the most common interview bug. Memorize one template (we use the half-open one) and never deviate.
6. C++/Java/Go integer overflow on (lo + hi) / 2 for very large constraints.
7. Calling feasible with the wrong arg type (e.g., float when int expected) in dynamically-typed languages — silent rounding.

Debugging Strategy

• Test feasible independently on the given examples for several values of C. The interactive trace feasible(15)=true, feasible(14)=false, … is your ground truth.
• Add an iteration counter to the binary search; cap it at 100. If the cap fires, your bounds or update direction is wrong.
• Print (lo, mid, hi, feasible(mid)) per iteration; the lo, hi interval should shrink monotonically to a singleton.
• For overflow suspicions, replace ints with long/long long/bigint and rerun.

Mastery Criteria

• Identified “minimum X such that property P” + monotone P as binary-search-on-answer in <60 seconds.
• Stated the monotonicity argument in plain English before coding.
• Wrote feasible first, tested it independently, then wrapped it in binary search.
• Used a single canonical binary-search template (half-open) without confusing < vs <=.
• Generalized verbally to LC 875 (Koko), LC 410 (Split Array Largest Sum), LC 1283 (Smallest Divisor) without prompting.
• Identified the language-specific overflow / template trap.
• Solved a similar new problem from this family in <10 minutes within a week of completing this lab.