Capacity To Ship Packages Within D Days
Problem
Given an array weights representing the weights of packages and an integer days, return the least weight capacity of a ship that will result in all the packages being shipped within days days.
- 1 ≤ days ≤ weights.length ≤ 5 * 10⁴
- 1 ≤ weights[i] ≤ 500
Example
weights = [1,2,3,4,5,6,7,8,9,10], days = 515A brute-force approach would try every capacity from the heaviest package (10) up to the sum of all weights (55), checking if the packages can be shipped within 5 days. For capacity 15, the ship can load packages as follows: Day 1: [1,2,3,4,5], total 15; Day 2: [6,7], total 13; Day 3: [8], total 8; Day 4: [9], total 9; Day 5: [10], total 10. This is the minimal capacity that allows shipping within 5 days.
Approach
Straightforward Solution
A brute-force approach tries every capacity from max(weights) to sum(weights), simulating the shipping process for each capacity. This approach is O(n * sum(weights)) and is too slow for large inputs.
Core Observation
The minimal ship capacity must be at least the heaviest package and at most the sum of all package weights. The problem reduces to finding the smallest capacity in this range that allows shipping within the given days.
Path to Optimal
PreviewRecognizing that the feasibility of shipping within days is a monotonic predicate with respect to capacity allows the use of binary search. If a capacity can ship within days, any larger capacity can also ship within days…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse binary search between max(weights) and sum(weights). For each mid capacity, simulate shipping by accumulating package weights until exceeding capacity, then increment day count…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n log S)
Where n is the number of packages and S is the sum of weights. Each binary search iteration takes O(n) to simulate shipping, and the search space is at most sum(weights), leading to O(log S) iterations.
Space
O(1)
Only a few variables are used for counters and boundaries; no additional data structures proportional to input size are needed.
Pattern Spotlight
Binary Search on Answer Space (Feasibility Check)
When the problem asks for a minimal or maximal value satisfying a monotonic feasibility condition, use binary search on the answer space by defining a predicate that checks feasibility and narrowing the search range accordingly.
Solution
| 1 | class Solution: |
| 2 | def shipWithinDays(self, weights: List[int], days: int) -> int: |
| 3 | def canShip(capacity): |
| 4 | used_days = 1 |
| 5 | curr_weight = 0 |
| 6 | |
| 7 | for weight in weights: |
| 8 | if curr_weight + weight > capacity: |
| 9 | used_days += 1 |
| 10 | curr_weight = 0 |
| 11 | |
| 12 | curr_weight += weight |
| 13 | |
| 14 | return used_days <= days |
| 15 | |
| 16 | l, r = max(weights), sum(weights) |
| 17 | |
| 18 | while l < r: |
| 19 | capacity = (l + r) // 2 |
| 20 | |
| 21 | if canShip(capacity): |
| 22 | r = capacity |
| 23 | else: |
| 24 | l = capacity + 1 |
| 25 | |
| 26 | return l |
Step-by-Step Solution
Simulate Shipping to Check Feasibility of Capacity
| 3 | def canShip(capacity): |
| 4 | used_days = 1 |
| 5 | curr_weight = 0 |
| 7 | for weight in weights: |
| 8 | if curr_weight + weight > capacity: |
| 9 | used_days += 1 |
| 10 | curr_weight = 0 |
| 12 | curr_weight += weight |
| 14 | return used_days <= days |
Objective
To determine if all packages can be shipped within the given days using a specified ship capacity.
Key Insight
By iterating through the package weights and accumulating them until the capacity is exceeded, the algorithm counts how many days are needed to ship all packages. This simulation directly tests the feasibility predicate required for binary search. It leverages the problem's sequential loading constraint and ensures that the capacity is respected daily.
Interview Quick-Check
Core Logic
The simulation accumulates package weights until exceeding capacity, then increments the day count and resets the current load, effectively partitioning packages into days.
State & Boundaries
Initialize used_days to 1 and curr_weight to 0 to represent the first day and current load.
Common Pitfalls & Bugs
Forgetting to reset curr_weight after incrementing used_days leads to incorrect day counts.
Apply Binary Search to Find Minimal Feasible Capacity
To efficiently narrow down the minimal ship capacity that allows shipping within the given days using binary search.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
return used_days <= daysReturn whether the total days used is within the allowed days.
This boolean result serves as the feasibility predicate for binary search, determining if the capacity is sufficient.
return lReturn the minimal capacity found after binary search completes.
At loop termination, left equals the minimal feasible capacity, which is the problem's solution.
if curr_weight + weight > capacity:Check if adding the current package exceeds the capacity.
This condition detects when the current day's load would surpass the ship's capacity, triggering a day increment.
Full line-by-line criticality + rationale for all 17 lines available on Pro.
Test Your Understanding
Why is binary search applicable on the capacity range, and how does the feasibility check ensure correctness?
See the answer with Pro.
Related Problems
Modified Binary Search pattern
Don't just read it. Drill it.
Reconstruct Capacity To Ship Packages Within D Days from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Capacity To Ship Packages Within D Days drill