Watch 10 video solutions for Capacity To Ship Packages Within D Days, a medium level problem involving Array, Binary Search. This walkthrough by take U forward has 236,349 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 Output: 15 Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1, 2, 3, 4, 5 2nd day: 6, 7 3rd day: 8 4th day: 9 5th day: 10 Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
Example 2:
Input: weights = [3,2,2,4,1,4], days = 3 Output: 6 Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this: 1st day: 3, 2 2nd day: 2, 4 3rd day: 1, 4
Example 3:
Input: weights = [1,2,3,1,1], days = 4 Output: 3 Explanation: 1st day: 1 2nd day: 2 3rd day: 3 4th day: 1, 1
Constraints:
1 <= days <= weights.length <= 5 * 1041 <= weights[i] <= 500Problem Overview: You are given an array weights where each element represents the weight of a package on a conveyor belt. Packages must be shipped in order. The task is to find the minimum ship capacity required so all packages are delivered within D days.
Approach 1: Binary Search on Capacity (O(n log S) time, O(1) space)
The key observation: if a ship capacity C can deliver all packages within D days, then any capacity greater than C will also work. This monotonic property allows you to apply binary search on the answer. The lower bound is the maximum weight in the array (a ship must carry the heaviest package), and the upper bound is the sum of all weights (ship everything in one day). For each candidate capacity, simulate the shipping process: iterate through the array and accumulate weights until exceeding the capacity, then increment the day counter and start a new load. If the number of days needed is ≤ D, reduce the search range; otherwise increase the capacity.
This approach combines binary search with a linear feasibility check over the array. Each check runs in O(n), and binary search runs over the capacity range up to the total weight, giving overall complexity O(n log S), where S is the sum of all weights.
Approach 2: Greedy Simulation (O(n * S) time, O(1) space)
A straightforward approach tries capacities sequentially starting from the maximum package weight. For each capacity, simulate the shipping process using a greedy rule: keep adding packages to the current day's load until the next package would exceed the capacity, then move to the next day. If all packages are delivered within D days, that capacity works. Otherwise increase the capacity and repeat.
This method uses the same greedy loading logic but without the search optimization. In the worst case you may test many capacities between the maximum weight and total weight, which leads to O(n * S) time complexity. The idea is simple and useful for understanding the feasibility check that powers the optimized solution.
Recommended for interviews: The expected solution is the binary search approach. Interviewers look for recognition of the monotonic search space and the ability to combine binary search with a greedy feasibility check. Showing the greedy simulation first demonstrates understanding of the shipping constraint, while the binary search optimization shows strong problem-solving and algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Simulation (Sequential Capacity Check) | O(n * S) | O(1) | When building intuition for the feasibility check or when constraints are very small |
| Binary Search on Capacity + Greedy Check | O(n log S) | O(1) | Optimal solution for large inputs; exploits monotonic capacity feasibility |