Capacity To Ship Packages Within D Days
Medium · Binary Search · Explanation and code example
Binary Search
How it works
Instead of checking every capacity linearly, we can use binary search because the problem has a monotonic property: if a capacity works, any larger capacity will also work. The search space ranges from the maximum package weight (minimum valid capacity) to the sum of all weights (shipping everything in one day). For each mid-point capacity, we check if it allows shipping within the day limit and adjust our search accordingly.
Steps
- Set the binary search range:
left= max(weights),right= sum(weights). - While
left<=right:- Calculate
mid= (left+right) / 2. - Simulate shipping with capacity
midby greedily filling each day's ship. - If we can ship within the allowed days, update the result and search the left half (
r=mid- 1). - Otherwise, search the right half (
l=mid+ 1).
- Calculate
- Return the minimum valid capacity found.
Complexity
- Time complexity:
O(n log n) - Space complexity:
O(1)
Things to watch for
Wrong Binary Search Bounds
The minimum capacity must be at least max(weights) (to ship the heaviest package), and the maximum is sum(weights) (ship everything in one day). Starting from 0 or 1 leads to invalid states where some packages cannot be shipped.
Miscounting Days in Simulation
A common mistake is not counting the first day or incrementing the day counter at the wrong time. The ship starts with capacity available on day 1, and a new day begins when the current package cannot fit.
Using Incorrect Binary Search Condition
This is a "find minimum satisfying condition" problem. When the capacity works, you should search left (r = mid - 1) to find smaller valid capacities. Searching right instead returns a suboptimal answer.
Python code example
from typing import List
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
l, r = max(weights), sum(weights)
res = r
def canShip(cap):
ships, currCap = 1, cap
for w in weights:
if currCap - w < 0:
ships += 1
if ships > days:
return False
currCap = cap
currCap -= w
return True
while l <= r:
cap = (l + r) // 2
if canShip(cap):
res = min(res, cap)
r = cap - 1
else:
l = cap + 1
return res
C++ code example
class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
int l = *max_element(weights.begin(), weights.end());
int r = accumulate(weights.begin(), weights.end(), 0);
int res = r;
while (l <= r) {
int cap = (l + r) / 2;
if (canShip(weights, days, cap)) {
res = min(res, cap);
r = cap - 1;
} else {
l = cap + 1;
}
}
return res;
}
private:
bool canShip(const vector<int>& weights, int days, int cap) {
int ships = 1, currCap = cap;
for (int w : weights) {
if (currCap - w < 0) {
ships++;
if (ships > days) {
return false;
}
currCap = cap;
}
currCap -= w;
}
return true;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.