Example 1
ready- Input
weights = [ 1, 2, 3, 1, 1 ] days = 4- Expected
3- Why
- capacity 3 ships the ordered groups [1,2], [3], [1,1]
Minimum Shipping Capacity
35 min · shipWithinDays()mediumOpen in LeetCode #1011 ↗
A ship that's too small misses the deadline; a ship that's too large wastes capacity. Your job is to find the exact boundary.
Packages wait in the order given by weights. Each day, load a contiguous group —
adjacent packages from the front of those still waiting — without exceeding one fixed
ship capacity. Return the smallest capacity that sends every package within days days.
A few ground rules:
- Package order can't change, and no package can be split.
- The ship uses the same capacity every day.
daysis at most the number of packages, so the schedule always contains work.
Constraints
1 <= weights.length <= 100_0001 <= days <= weights.length1 <= weights[i] <= 500
Hints
Test one capacity greedily
Walk through the packages in order. Keep loading the current day until the next package would exceed the capacity, then start a new day with that package.
Fence the answer
The capacity can't be below the heaviest package. The sum of every weight is always enough because it ships everything in one day.
Search the first success
If a capacity meets the deadline, every larger capacity does too. Binary search for
the smallest capacity whose greedy schedule uses at most days days.
Follow-up
Why does filling each day as much as possible minimize the number of days for a fixed capacity?
Visible cases
Examples
Example 2
ready- Input
weights = [ 3, 2, 2, 4, 1, 4 ] days = 3- Expected
6- Why
- capacity 6 is the first capacity that fits three days
Example 3
ready- Input
weights = [ 5, 8, 2 ] days = 1- Expected
15- Why
- one day must carry the full total weight
Interview signal
Asked at
AmazonGoogleMicrosoft
Try every capacity
The answer lies between the heaviest package and the total weight. Test each integer in that range, using an in-order greedy packing pass to count days.
def ship_within_days(weights: list[int], days: int) -> int:
def days_needed(capacity: int) -> int:
used, load = 1, 0
for weight in weights:
if load + weight > capacity:
used += 1
load = 0
load += weight
return used
for capacity in range(max(weights), sum(weights) + 1):
if days_needed(capacity) <= days:
return capacity
return sum(weights)Time O(n · S). Space O(1). Here S is the total weight; a wide capacity range makes
the one-by-one scan unusable.
Binary search capacity
For a fixed capacity, greedily fill each day before opening the next one. Stopping a day earlier can't help: it only moves weight into later days. This pass therefore gives the fewest days possible at that capacity.
A capacity is feasible when its greedy schedule meets the deadline. Once one capacity is feasible, every larger capacity is too, so search for the first feasible integer.
def ship_within_days(weights: list[int], days: int) -> int:
def days_needed(capacity: int) -> int:
used, load = 1, 0
for weight in weights:
if load + weight > capacity:
used += 1
load = 0
load += weight
return used
left, right = max(weights), sum(weights)
while left < right:
middle = left + (right - left) // 2
if days_needed(middle) <= days:
right = middle
else:
left = middle + 1
return leftKeeping a feasible middle with right = middle matters: it may be the minimum. A
failed middle can be discarded with every smaller capacity.
Time O(n log S). Space O(1). Each binary-search step runs one O(n) packing pass.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
3
Run: visible + custom · Submit: full suite