Capacity To Ship Packages Within D Days

mediumBinary Search258 stepsJava · Python · C++

Find the smallest ship capacity that ships all packages, in order, within days. The answer lies between the heaviest package and the total weight. For a candidate capacity, greedily fill each day; binary search the smallest capacity that needs ≤ days.

▶ Watch the animated trace

Traced input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5 → 15. Original problem: neetcode.io/problems/capacity-to-ship-packages-within-d-days

Complexity

BestO(n log S)

AverageO(n log S)

WorstO(n log S)

SpaceO(1)

S = sum of weights. Each check is a greedy pass.

Key idea

Lower bound is max(weights): the heaviest package must fit.
Upper bound is sum(weights): everything in one day.
Greedy check: load packages until the next one won't fit, then start a new day.
Bigger capacity never needs more days, so binary search applies.

Common mistakes

Starting lo at 1 lets capacities smaller than one package "work" in the check.
Reordering packages; they must ship in the given order.

Solution

Java

int shipWithinDays(int[] weights, int days) {
    int lo = 0, hi = 0;
    for (int w : weights) { lo = Math.max(lo, w); hi += w; }
    while (lo < hi) {
        int cap = lo + (hi - lo) / 2;
        int need = daysNeeded(weights, cap);
        if (need <= days) hi = cap;
        else lo = cap + 1;
    }
    return lo;
}

int daysNeeded(int[] weights, int cap) {
    int d = 1, load = 0;
    for (int w : weights) {
        if (load + w > cap) { d++; load = 0; }
        load += w;
    }
    return d;
}

Python

def shipWithinDays(weights: List[int], days: int) -> int:
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        cap = (lo + hi) // 2
        need = daysNeeded(weights, cap)
        if need <= days: hi = cap
        else: lo = cap + 1
    return lo


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

C++

int daysNeeded(vector<int>& weights, int cap);

int shipWithinDays(vector<int>& weights, int days) {
    int lo = 0, hi = 0;
    for (int w : weights) { lo = max(lo, w); hi += w; }
    while (lo < hi) {
        int cap = lo + (hi - lo) / 2;
        int need = daysNeeded(weights, cap);
        if (need <= days) hi = cap;
        else lo = cap + 1;
    }
    return lo;
}

int daysNeeded(vector<int>& weights, int cap) {
    int d = 1, load = 0;
    for (int w : weights) {
        if (load + w > cap) { d++; load = 0; }
        load += w;
    }
    return d;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
One day Everything at once: the total weight.	`weights = [3, 2, 2, 4, 1, 4], days = 1`	`16`
A day per package The heaviest package sets the capacity.	`weights = [1, 2, 3], days = 3`	`3`
More days than packages Extra days don't help below the heaviest package.	`weights = [5, 1], days = 10`	`5`
Classic [1, 2], [3], [1, 1] fits in 3 days at capacity 3.	`weights = [1, 2, 3, 1, 1], days = 4`	`3`