Workspace

Problem workspace

3 day streakD

Capacity to Ship Packages Within D Days

MediumBinary SearchSearch on the answer

The challenge

Find the minimum capacity that ships all packages in their given order within D days.

Nonempty positive integer weights and D ≥ 1. Invalid D returns −1. Total weight fits a signed 64-bit integer.

Example

[1, 2, 3, 1, 1], D = 4 → capacity 3.

Use the walkthrough below to inspect the input and each state change.

See Minimum shipping capacity, step by step

Inspect the comparison, the invariant, and the next boundary.

Answer-space searchD = 4
left3candidate—right8Search candidate values, not input indices
1021321314
Tested candidate / qualifying inputResolved positionParameters shown above
Left
3
Middle
—
Right
8
Step 01 / 5

Search the answer range

The candidate is a number, rather than an input index. Keep the smallest feasible value.

left = 3; right = 8

Recorded result so far

Not resolved
View exact input

Input: [1,2,3,1,1] · D = 4

Put it into code

Greedily fill each day until the next package would exceed capacity. Larger capacities cannot need more days.

Indices are zero-based. C++ uses C++17 or later.

def ship_capacity(nums, days):
    # Nonempty positive weights, kept in input order.
    if days < 1:
        return -1
    left, right = max(nums), sum(nums)
    while left < right:
        mid = left + (right - left) // 2
        parts, load = 1, 0
        for value in nums:
            if load + value > mid:
                parts += 1
                load = 0
            load += value
        if parts <= days:
            right = mid
        else:
            left = mid + 1
    return left

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap