Capacity to Ship Packages: The Same Search, New Costume

If you interview at Amazon, Google, Flexport, expect some version of "Capacity to Ship Packages Within D Days". It is rated Medium, and it falls squarely into the Modified Binary Search pattern — pattern-first preparation beats grinding random problems every time. Part 9 of 11 in the Modified Binary Search arc.

The Problem

A conveyor belt has weights that must ship in order within days days; each day you load consecutively without exceeding the ship's capacity. Return the minimum capacity that makes the deadline. Koko with one twist: the checker greedily packs prefixes instead of dividing pile sizes.

Input:  weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Output: 15
Days: [1..5], [6, 7], [8], [9], [10].

Recognizing the Modified Binary Search Pattern

Binary search is not about sorted arrays — it is about any monotonic predicate: if the answer space splits into a false-region followed by a true-region, you can halve it. FAANG interviews rarely ask the textbook version; they ask rotated arrays, boundary-finding, and search-on-the-answer problems where the array being searched is conceptual. Getting the loop invariant right is the whole game.

Bigger ships never need more days — monotonic feasibility again. The interesting half moves into the checker: greedy load-until-overflow is provably optimal for counting days at a fixed capacity, because deferring any item never helps.

The Approach

Search capacity in [max(weights), sum(weights)] — the smallest bound that can carry the heaviest item, and the capacity that finishes in one day. The checker simulates: accumulate until adding the next weight would overflow, then start a new day.

Getting the lower bound right matters: starting from 1 makes the checker divide by loads it can never carry and silently produces wrong day counts. Bounds are part of the answer, not setup trivia.

Python Solution

def ship_within_days(weights: list[int], days: int) -> int:
    """Minimum capacity shipping all weights, in order, within days."""

    def days_needed(cap: int) -> int:
        d, load = 1, 0
        for w in weights:
            if load + w > cap:
                d += 1
                load = 0
            load += w
        return d

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(mid) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo

Complexity

• Time: O(n log S) — n weights per check, S the weight-sum range being halved
• Space: O(1) — streaming simulation

Interview Tips and Follow-Ups

• Why is greedy packing optimal for the checker? Exchange argument: moving an item to an earlier day never increases day count. One sentence, big credit.
• Split Array Largest Sum is this problem verbatim with different words — solving one solves both, and saying so is the point.
• The in-order constraint is what forbids bin-packing cleverness; if items could reorder, the problem becomes NP-hard bin packing — a sharp observation interviewers remember.

If this clicked, continue the Modified Binary Search arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.