Capacity To Ship Packages Within D Days
Asked at Amazon
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.
Asked At
| 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.
Visual walkthrough for weights = [3, 2, 2, 4, 1, 4], days = 3:
- lo = max 4, hi = sum 16.
- mid 10 -> days 2 (loads 7, 9), feasible -> hi = 10.
- mid 7 -> days 3 (7, 5, 4), feasible -> hi = 7.
- mid 5 -> days 4 (5, 2, 5, 4), infeasible -> lo = 6.
- mid 6 -> days 3 (5, 6, 5), feasible -> hi = 6.
Answer: 6.
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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.