Problem statement

Packages must be shipped in order within days days. Each day the ship loads consecutive packages up to its weight capacity.

Return the least capacity that ships everything within days days.

Example 1

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

Example 2

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6

Constraints

• 1 <= weights.length <= 25
• 1 <= days <= weights.length
• 1 <= weights[i] <= 500

Hints for Capacity To Ship Packages Within D Days

1. Hint 1

   For a fixed capacity, greedily fill each day — that gives the days needed, monotone in capacity.

2. Hint 2

   Binary search capacity between max(weights) and sum(weights).

How to solve Capacity To Ship Packages Within D Days

Another binary search over the answer. For a fixed capacity you can compute the days needed greedily — keep loading the next package while it fits, otherwise start a new day — and that day count only falls as capacity rises. So the workable capacities form an upward-closed range, and the answer is its lower boundary.

Approach

1. The capacity must be at least max(weights) (a package must fit on some day) and never needs to exceed sum(weights) (one day for everything).
2. For a candidate capacity, sweep the packages in order, accumulating the current day's load.
3. When adding a package would exceed the capacity, close the day, start a new one, and put the package there.
4. If the resulting day count is at most days, the capacity works — search lower; otherwise search higher.
5. The search converges on the least workable capacity.

Why it works

The greedy day count is optimal for a fixed capacity: since packages must ship in order, delaying a package that still fits can never reduce the number of days — it only pushes work later. So the greedy sweep computes the true minimum days, making the feasibility test exact. That test is monotone in capacity, which is what licenses the binary search. The lower bound of max(weights) matters because any smaller capacity makes the problem impossible, not merely slow.

Complexity

• Time — O(n log(sum of weights))
• Space — O(1)

Pitfalls

• Start the range at max(weights), not 1 — below that no number of days suffices and the day count is meaningless.
• Packages ship in order; you may not reorder or repack them, which is why the greedy is valid.
• Begin the day counter at 1, not 0 — you are already loading the first day when the sweep starts.
• Keep mid in range on success (hi = mid), since it may itself be the minimum.

Reference solution

Python

from typing import List

def shipWithinDays(weights: List[int], days: int) -> int:
    def days_needed(cap: int) -> int:
        d = 1
        load = 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

Java

public static int shipWithinDays(int[] weights, int days) {
    int lo = 0, hi = 0;
    for (int w : weights) {
        if (w > lo) lo = w;
        hi += w;
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int used = 1, load = 0;
        for (int w : weights) {
            if (load + w > mid) {
                used++;
                load = 0;
            }
            load += w;
        }
        if (used <= days) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

C++

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

JavaScript

var shipWithinDays = function(weights, days) {
    function daysNeeded(cap) {
        let d = 1, load = 0;
        for (const w of weights) {
            if (load + w > cap) { d++; load = 0; }
            load += w;
        }
        return d;
    }
    let lo = Math.max.apply(null, weights);
    let hi = weights.reduce(function(a, b) { return a + b; }, 0);
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (daysNeeded(mid) <= days) hi = mid;
        else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium