Capacity To Ship Packages Within D Days (LC 1011)
A conveyor belt lines up packages that must all ship out within days days. The i-th package weighs weights[i]; each day you load the ship with the next packages in belt order, but the total you load in a single day can never exceed the ship's weight capacity.
Find the smallest ship capacity that still gets every package shipped within days days.
Worked Examples
weights = [1,2,3,4,5,6,7,8,9,10], days = 51515, the days can be 1+2+3+4+5 = 15, 6+7 = 13, 8, 9, 10: exactly 5 days. With capacity 14, the same rule needs 6 days, so 15 is the smallest capacity that works.weights = [3,2,2,4,1,4], days = 36weights = [1,2,3,1,1], days = 43⚖️Formal Constraints & Bounds
1 <= days <= weights.length <= 5 * 1041 <= weights[i] <= 500
Core Insight
The answer is a number you choose, not an index. The check can_ship simulates the task for one capacity, and more capacity never needs more days, so the answers are False and then True and Lower Bound finds the first True.
Real-World Scenario & Production Applications
Autoscaling container clusters and shipping logistics: determining the minimum server capacity or cargo fleet size to handle traffic spikes within guaranteed SLA deadlines.
Subproblems & Recurrence Decomposition3 Phases
Write the check can_ship(capacity) first. One pass packs the packages in order: a package that is heavier than the ship makes the check False, a package that would overflow the day starts a new day, and the check returns days_needed <= days.
def can_ship(capacity):
days_needed, load = 1, 0
for w in weights:
if w > capacity:
return False
if load + w > capacity:
days_needed += 1
load = 0
load += w
return days_needed <= daysStep-by-Step Execution Trace Table
| Step | Range [lo, hi) | mid (capacity) | The check can_ship(mid) | Decision | New range [lo, hi) |
|---|---|---|---|---|---|
| 1 | [1, 9) | 5 | Day 1: 1 + 2 = 3. Package 3 would make 6, so day 2 starts: 3 + 1 + 1 = 5. Days needed: 2, and 2 <= 4 → True | mid may be the smallest: hi = mid | [1, 5) |
| 2 | [1, 5) | 3 | Day 1: 1 + 2 = 3. Package 3 would make 6, so day 2: 3. Package 1 would make 4, so day 3: 1 + 1 = 2. Days needed: 3, and 3 <= 4 → True | hi = mid | [1, 3) |
| 3 | [1, 3) | 2 | The package of weight 3 is larger than 2, so the guard w > capacity returns → False | every capacity up to 2 is too small: lo = mid + 1 | [3, 3) |
| 4 | [3, 3) | The range is empty. Lower Bound returns 3. |
The trace for weights = [1, 2, 3, 1, 1] and days = 4, step by step:
- The total weight is 8, so the candidates are the capacities 1 to 8. The range is
[1, 9). - Step 1 tests capacity 5. The packages ship in 2 days, which is at most 4, so 5 works and we keep it with
hi = mid. - Step 2 tests capacity 3. The packages ship in 3 days, so 3 works too, and we keep it.
- Step 3 tests capacity 2. The package of weight 3 does not fit on a ship with capacity 2, so the check is False. Capacities 1 and 2 are too small, so
lo = mid + 1 = 3. - Step 4:
lois equal tohi, so the answer is 3.
| 1 | def can_ship(capacity: int) -> bool: |
| 2 | days_needed, load = 1, 0 |
| 3 | for w in weights: |
| 4 | if w > capacity: |
| 5 | return False |
| 6 | if load + w > capacity: |
| 7 | days_needed += 1 |
| 8 | load = 0 |
| 9 | load += w |
| 10 | return days_needed <= days |
| 11 | lo = 1 |
| 12 | hi = sum(weights) + 1 |
| 13 | return binary_search_lower_bound(lo, hi, can_ship) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Some answers are not in the input. They are a number you choose: a capacity, a speed, a number of days. The only way to test a number is to run the task with it. So the check is a simulation, and Lower Bound searches the numbers themselves. For Capacity To Ship Packages Within D Days (LC 1011), the check asks: can the packages ship within days days with this capacity?
🚢 The Analogy: Choosing The Size Of A Ship
Imagine you must pick the smallest ship that carries all packages, in belt order, within a deadline. You cannot read the answer from a list. You can only try a ship size and count the days. If a ship of size 15 is enough, a ship of size 16 is enough too. So the sizes that fail come first, and the sizes that work come after them. The smallest size that works is the boundary.
🔑 Why It Works
The simulation answers the question exactly for one capacity. More capacity never needs more days, so the row of answers is False and then True, and Lower Bound finds the first True. The total weight always works, so it is a safe end of the range. The guard w > capacity matters: without it, a ship smaller than one package is reported as working.
Lower bound set below maximum single item: Setting
lo = 0orlo = 1allows candidate capacities smaller than the heaviest package, which can never be shipped. Lower bound must strictly bemax(weights).Upper bound set too low: The worst-case upper bound is when all packages are shipped on a single day.
himust be initialized tosum(weights).Off-by-one day counter in greedy feasibility check: Initializing
days_needed = 0instead of1underestimates the day count by 1. A new non-empty allocation always requires at least day 1.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Find the smallest ship capacity that still gets every package shipped within days days": the smallest value that passes a check, and a bigger capacity never needs more days, so binary search the capacities (Feasible Function).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: every capacity before lo fails can_ship, and every capacity from hi on passes it, so the smallest passing capacity is between lo and hi. More capacity never needs more days, so the answers read False, then True.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Leaving out the guard
w > capacity: a ship smaller than one package is reported as working, soweights = [5],days = 2returns1instead of5.Setting
hitoo low: withhi = max(weights), the running input returns10instead of15, because every capacity below 15 fails.Day counting:
days_neededstarts at1, and the test isdays_needed <= days. Starting at0counts a day too few, and==rejects a big ship that needs fewer days.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"This is a Feasible Function search. The answer is a capacity, not an index, so I write the check can_ship as a simulation: fill each day until the next package would overflow, count the days, and return days_needed <= days. A package that is heavier than the ship makes the check return False. More capacity never needs more days, so the answers are False and then True, and I run Lower Bound over the capacities from 1 to sum(weights) + 1. The total weight always works, so it is a safe end of the range. The trap is leaving out the guard for a package that is heavier than the ship. That is O(N log S) time, with S the total weight, and
O(1)space."
Complexity & Mathematical Proof
O(N * log(sum(weights)))
Look at the structure: Lower Bound runs while lo < hi: over the capacities [1, sum(weights) + 1). Each pass halves the range, so it runs at most about log2(S) + 1 passes, with S = sum(weights). Each pass calls can_ship(mid), and that call runs one for w in weights: loop over all N packages in O(N) time. N work per pass times log S passes gives O(N log S) time.
O(1)
Look at the memory used: both Lower Bound and the check are iterative, so the call stack holds a few frames. Inside can_ship we keep only two integers, days_needed and load. Auxiliary space is O(1).
Derivation Progression
Range = [1, ∑ W + 1)
The smallest capacity to try is 1, and the total weight always works, so the range is [1, sum(weights) + 1).
O(N) linear scan
for w in weights: loop packs packages greedily into the current day in O(N) time.
O(N · log(∑ W))
Lower Bound runs about log2(sum W) passes, and each pass runs the O(N) check once.
Variable Definitions
Total number of package items in array
Total sum of all package weights in the array
Maximum single package weight
Memory Architecture & Bounds
O(1) Iterative while loop with zero recursion frames
O(1) Only scalar accumulators in CPU registers
O(1) Returns optimal minimum integer capacity
Boundary Best / Worst Cases
— Fixed number of binary search iterations.
.
— Standard binary search on integer domain.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The statement asks for "the smallest ship capacity that still gets every package shipped within days days." The answer is a number you choose, not an index, and checking one number means running the task with it. A bigger capacity never needs more days. This is a Feasible Function search: Lower Bound over the capacities, with a simulation as the check.
With up to packages of weight at most , sum(weights) is at most , so the range [1, sum(weights) + 1) needs only about checks of each. The guard w > capacity makes the check False for a capacity below the heaviest package, so the range can start at 1.
Leaving out the guard w > capacity is the trap: a package that is heavier than the ship opens a new day and is still loaded, so a too-small capacity looks like it works. Two edge cases pin the answer: when days == len(weights), the answer is max(weights), and when days == 1, the ship must take sum(weights) at once. Both are inside the range, so the search returns them without a special case.
Capacity To Ship Packages Within D Days (LC 1011)
A conveyor belt lines up packages that must all ship out within days days. The i-th package weighs weights[i]; each day you load the ship with the next packages in belt order, but the total you load in a single day can never exceed the ship's weight capacity.
Find the smallest ship capacity that still gets every package shipped within days days.
Worked Examples
weights = [1,2,3,4,5,6,7,8,9,10], days = 51515, the days can be 1+2+3+4+5 = 15, 6+7 = 13, 8, 9, 10: exactly 5 days. With capacity 14, the same rule needs 6 days, so 15 is the smallest capacity that works.weights = [3,2,2,4,1,4], days = 36weights = [1,2,3,1,1], days = 43⚖️Formal Constraints & Bounds
1 <= days <= weights.length <= 5 * 1041 <= weights[i] <= 500
Core Insight
The answer is a number you choose, not an index. The check can_ship simulates the task for one capacity, and more capacity never needs more days, so the answers are False and then True and Lower Bound finds the first True.
Real-World Scenario & Production Applications
Autoscaling container clusters and shipping logistics: determining the minimum server capacity or cargo fleet size to handle traffic spikes within guaranteed SLA deadlines.
Subproblems & Recurrence Decomposition3 Phases
Write the check can_ship(capacity) first. One pass packs the packages in order: a package that is heavier than the ship makes the check False, a package that would overflow the day starts a new day, and the check returns days_needed <= days.
def can_ship(capacity):
days_needed, load = 1, 0
for w in weights:
if w > capacity:
return False
if load + w > capacity:
days_needed += 1
load = 0
load += w
return days_needed <= daysStep-by-Step Execution Trace Table
| Step | Range [lo, hi) | mid (capacity) | The check can_ship(mid) | Decision | New range [lo, hi) |
|---|---|---|---|---|---|
| 1 | [1, 9) | 5 | Day 1: 1 + 2 = 3. Package 3 would make 6, so day 2 starts: 3 + 1 + 1 = 5. Days needed: 2, and 2 <= 4 → True | mid may be the smallest: hi = mid | [1, 5) |
| 2 | [1, 5) | 3 | Day 1: 1 + 2 = 3. Package 3 would make 6, so day 2: 3. Package 1 would make 4, so day 3: 1 + 1 = 2. Days needed: 3, and 3 <= 4 → True | hi = mid | [1, 3) |
| 3 | [1, 3) | 2 | The package of weight 3 is larger than 2, so the guard w > capacity returns → False | every capacity up to 2 is too small: lo = mid + 1 | [3, 3) |
| 4 | [3, 3) | The range is empty. Lower Bound returns 3. |
The trace for weights = [1, 2, 3, 1, 1] and days = 4, step by step:
- The total weight is 8, so the candidates are the capacities 1 to 8. The range is
[1, 9). - Step 1 tests capacity 5. The packages ship in 2 days, which is at most 4, so 5 works and we keep it with
hi = mid. - Step 2 tests capacity 3. The packages ship in 3 days, so 3 works too, and we keep it.
- Step 3 tests capacity 2. The package of weight 3 does not fit on a ship with capacity 2, so the check is False. Capacities 1 and 2 are too small, so
lo = mid + 1 = 3. - Step 4:
lois equal tohi, so the answer is 3.
| 1 | def can_ship(capacity: int) -> bool: |
| 2 | days_needed, load = 1, 0 |
| 3 | for w in weights: |
| 4 | if w > capacity: |
| 5 | return False |
| 6 | if load + w > capacity: |
| 7 | days_needed += 1 |
| 8 | load = 0 |
| 9 | load += w |
| 10 | return days_needed <= days |
| 11 | lo = 1 |
| 12 | hi = sum(weights) + 1 |
| 13 | return binary_search_lower_bound(lo, hi, can_ship) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Some answers are not in the input. They are a number you choose: a capacity, a speed, a number of days. The only way to test a number is to run the task with it. So the check is a simulation, and Lower Bound searches the numbers themselves. For Capacity To Ship Packages Within D Days (LC 1011), the check asks: can the packages ship within days days with this capacity?
🚢 The Analogy: Choosing The Size Of A Ship
Imagine you must pick the smallest ship that carries all packages, in belt order, within a deadline. You cannot read the answer from a list. You can only try a ship size and count the days. If a ship of size 15 is enough, a ship of size 16 is enough too. So the sizes that fail come first, and the sizes that work come after them. The smallest size that works is the boundary.
🔑 Why It Works
The simulation answers the question exactly for one capacity. More capacity never needs more days, so the row of answers is False and then True, and Lower Bound finds the first True. The total weight always works, so it is a safe end of the range. The guard w > capacity matters: without it, a ship smaller than one package is reported as working.
Lower bound set below maximum single item: Setting
lo = 0orlo = 1allows candidate capacities smaller than the heaviest package, which can never be shipped. Lower bound must strictly bemax(weights).Upper bound set too low: The worst-case upper bound is when all packages are shipped on a single day.
himust be initialized tosum(weights).Off-by-one day counter in greedy feasibility check: Initializing
days_needed = 0instead of1underestimates the day count by 1. A new non-empty allocation always requires at least day 1.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Find the smallest ship capacity that still gets every package shipped within days days": the smallest value that passes a check, and a bigger capacity never needs more days, so binary search the capacities (Feasible Function).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: every capacity before lo fails can_ship, and every capacity from hi on passes it, so the smallest passing capacity is between lo and hi. More capacity never needs more days, so the answers read False, then True.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Leaving out the guard
w > capacity: a ship smaller than one package is reported as working, soweights = [5],days = 2returns1instead of5.Setting
hitoo low: withhi = max(weights), the running input returns10instead of15, because every capacity below 15 fails.Day counting:
days_neededstarts at1, and the test isdays_needed <= days. Starting at0counts a day too few, and==rejects a big ship that needs fewer days.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"This is a Feasible Function search. The answer is a capacity, not an index, so I write the check can_ship as a simulation: fill each day until the next package would overflow, count the days, and return days_needed <= days. A package that is heavier than the ship makes the check return False. More capacity never needs more days, so the answers are False and then True, and I run Lower Bound over the capacities from 1 to sum(weights) + 1. The total weight always works, so it is a safe end of the range. The trap is leaving out the guard for a package that is heavier than the ship. That is O(N log S) time, with S the total weight, and
O(1)space."
Complexity & Mathematical Proof
O(N * log(sum(weights)))
Look at the structure: Lower Bound runs while lo < hi: over the capacities [1, sum(weights) + 1). Each pass halves the range, so it runs at most about log2(S) + 1 passes, with S = sum(weights). Each pass calls can_ship(mid), and that call runs one for w in weights: loop over all N packages in O(N) time. N work per pass times log S passes gives O(N log S) time.
O(1)
Look at the memory used: both Lower Bound and the check are iterative, so the call stack holds a few frames. Inside can_ship we keep only two integers, days_needed and load. Auxiliary space is O(1).
Derivation Progression
Range = [1, ∑ W + 1)
The smallest capacity to try is 1, and the total weight always works, so the range is [1, sum(weights) + 1).
O(N) linear scan
for w in weights: loop packs packages greedily into the current day in O(N) time.
O(N · log(∑ W))
Lower Bound runs about log2(sum W) passes, and each pass runs the O(N) check once.
Variable Definitions
Total number of package items in array
Total sum of all package weights in the array
Maximum single package weight
Memory Architecture & Bounds
O(1) Iterative while loop with zero recursion frames
O(1) Only scalar accumulators in CPU registers
O(1) Returns optimal minimum integer capacity
Boundary Best / Worst Cases
— Fixed number of binary search iterations.
.
— Standard binary search on integer domain.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The statement asks for "the smallest ship capacity that still gets every package shipped within days days." The answer is a number you choose, not an index, and checking one number means running the task with it. A bigger capacity never needs more days. This is a Feasible Function search: Lower Bound over the capacities, with a simulation as the check.
With up to packages of weight at most , sum(weights) is at most , so the range [1, sum(weights) + 1) needs only about checks of each. The guard w > capacity makes the check False for a capacity below the heaviest package, so the range can start at 1.
Leaving out the guard w > capacity is the trap: a package that is heavier than the ship opens a new day and is still loaded, so a too-small capacity looks like it works. Two edge cases pin the answer: when days == len(weights), the answer is max(weights), and when days == 1, the ship must take sum(weights) at once. Both are inside the range, so the search returns them without a special case.