Capacity to Ship Packages Within D Days — Medium Problem & Solution

Problem statement

Packages must be shipped in the given order within days days. Each day you load the ship with consecutive packages without exceeding its weight capacity.

Return the minimum capacity that gets every package shipped in time.

Example 1

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

Example 2

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

Example 3

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

Constraints

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

How to solve Capacity to Ship Packages Within D Days

Binary search on the answer. For a fixed capacity, the minimum number of days is obtained greedily — keep loading while it fits — and that count is non-increasing in the capacity, so the feasible capacities form a suffix.

Approach

1. Set lo to the maximum weight (anything smaller cannot carry that package) and hi to the total weight (one day suffices).
2. need(cap): sweep the weights, starting a new day whenever the next package would overflow.
3. Binary search the smallest cap with need(cap) <= days.

Why it works

The greedy day count is optimal for a fixed capacity: deferring a package that fits can only push work later and never reduces the number of days. Raising the capacity can only let more packages fit per day, so need is non-increasing — exactly the monotonicity binary search needs.

Complexity

• Time — O(n log W) where W is the total weight
• Space — O(1)

Pitfalls

• Starting lo at 1 lets the search consider capacities that can never carry the heaviest package; need must then be written not to loop forever.
• d starts at 1, not 0 — the first day is already in use.
• Splitting packages or reordering them is not allowed.

Reference solution

Python

from typing import List

def shipWithinDays(weights: List[int], days: int) -> int:
    lo, hi = max(weights), sum(weights)

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

    while lo < hi:
        mid = (lo + hi) // 2
        if need(mid) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var shipWithinDays = function(weights, days) {
    var lo = 0, hi = 0, i;
    for (i = 0; i < weights.length; i++) {
        if (weights[i] > lo) lo = weights[i];
        hi += weights[i];
    }
    var need = function(cap) {
        var d = 1, cur = 0;
        for (var j = 0; j < weights.length; j++) {
            if (cur + weights[j] > cap) { d++; cur = 0; }
            cur += weights[j];
        }
        return d;
    };
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (need(mid) <= days) hi = mid; else lo = mid + 1;
    }
    return lo;
};

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

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium