1011. Capacity To Ship Packages Within D Days
Asked at Amazon
Difficulty
Medium
Time
O(n log(sum(weights)))
Space
O(1)
Pattern
Array
Companies
1
Problem
You have a list of package weights, weights, sitting on a conveyor belt in a fixed order. You must ship all of them within days days. Each day the ship takes a contiguous block of packages from the front of the belt, in the given order. The total weight loaded on one day cannot exceed the ship's capacity.
Return the smallest ship capacity that lets you ship every package within days days.
Because the order is fixed, you cannot rearrange packages to pack days better. You only choose where each day ends. A capacity that works for days days also works for any larger number of days, which is the key property that makes this problem solvable quickly.
Ship in order, one block per day
Constraints
- ●
1 <= days <= weights.length <= 5 * 10^4 - ●
1 <= weights[i] <= 500
Examples
weights = [1,2,3,4,5,6,7,8,9,10], days = 515weights = [3,2,2,4,1,4], days = 36weights = [1,2,3,1,1], days = 43Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
How to Think About It
Baseline: try every capacity from the heaviest package to the total weight, simulating the day count for each. That is O(n * totalWeight), infeasible because the total weight reaches 5*10^8.
Key insight: the answer lies between max(weights) and sum(weights). Within that range the predicate "can ship in at most d days" is monotone - if capacity c works, any larger capacity also works, so binary search applies cleanly.
Feasibility check: pack greedily in order. Walk the weights accumulating the current day's load; if adding the next package would exceed the candidate capacity, start a new day carrying that package over.
Why the greedy check is correct: packages must ship in array order, so choosing the earliest possible day boundary can never increase the total number of days. Pack each day as full as possible.
Edge cases: days = 1 forces capacity = total weight; a single heavy package sets the lower bound by itself; equal weights make the binary search narrow in O(log sum) iterations.
Optimal Approach
Binary search the minimum capacity. The lower bound is the heaviest single package (a smaller ship could not move it) and the upper bound is the total weight (one ship carries everything). For each mid capacity, run the greedy shipping simulation: walk the weights, accumulate the current day load, and open a new day whenever the next package would overflow mid - that package starts the new day. Accept mid when its simulated day count is at most days.
Walkthrough for weights = [3, 2, 2, 4, 1, 4], days = 3:
- lo = max(weights) = 4, hi = sum(weights) = 16.
- mid = 10: day 1 = 7, day 2 = 9 -> 2 days, feasible, so hi = 10.
- mid = 7: day 1 = 7, day 2 = 5, day 3 = 4 -> 3 days, feasible, so hi = 7.
- mid = 5: day 1 = 5, day 2 = 2, day 3 = 5, day 4 = 4 -> 4 days, infeasible, so lo = 6.
- mid = 6: day 1 = 5, day 2 = 6, day 3 = 5 -> 3 days, feasible, so hi = 6. Answer 6.
Time: O(n log (sum(weights))) space: O(1), ignoring the output array.
Binary search the capacity
What Trips People Up in Real Interviews
Starting the low bound at 0 or 1 instead of max(weights). A ship smaller than the heaviest package can never move it - the feasibility check then over-counts days or errors. The low bound is max(weights).
Off-by-one in the day counter. Initialize days = 1 and increment only when a package would overflow, because the very first package needs a day. Starting at 0 under-reports and accepts infeasible capacities.
Dropping the overflowing package. When a package does not fit the current day, it is not lost - it must become the first package of the next day. Forgetting to carry it over inflates the true capacity.
Confusing this with split-array-largest-sum. The feasibility check is identical, but the requested output is the minimum capacity, so keep the binary search direction and the answer extraction straight.
Using linear search over capacity. With a sum near 5*10^8, a linear scan of every candidate is too slow; the monotone predicate makes binary search the expected O(n log sum) solution.
Solution Code
O(n log(sum(weights))) timedef shipWithinDays(weights, days):
def can_ship(capacity):
load = 0
needed_days = 1
for w in weights:
load += w
if load > capacity:
needed_days += 1
load = w
return needed_days <= days
lo = max(weights)
hi = sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if can_ship(mid):
hi = mid
else:
lo = mid + 1
return loFrequently Asked Questions
What is the Capacity To Ship Packages Within D Days problem?
A conveyor belt must ship package weights in their given order using a ship whose daily load cannot exceed a capacity, finishing inside d days. Find the minimum capacity that still meets the deadline - the canonical Amazon binary search on the answer.
How do you solve Capacity To Ship Packages Within D Days?
The optimal approach runs in O(n log(sum(weights))) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Capacity To Ship Packages Within D Days?
Capacity To Ship Packages Within D Days is asked at Amazon. It is a medium difficulty problem.
What are common mistakes on Capacity To Ship Packages Within D Days?
- Starting the low bound at 0 or 1 instead of max(weights). A ship smaller than the heaviest package can never move it - the feasibility check then over-counts days or errors. The low bound is max(weights).
- Off-by-one in the day counter. Initialize days = 1 and increment only when a package would overflow, because the very first package needs a day. Starting at 0 under-reports and accepts infeasible capacities.
- Dropping the overflowing package. When a package does not fit the current day, it is not lost - it must become the first package of the next day. Forgetting to carry it over inflates the true capacity.
- Confusing this with split-array-largest-sum. The feasibility check is identical, but the requested output is the minimum capacity, so keep the binary search direction and the answer extraction straight.
- Using linear search over capacity. With a sum near 5*10^8, a linear scan of every candidate is too slow; the monotone predicate makes binary search the expected `O(n log sum)` solution.