Capacity To Ship Packages Within D Days
Capacity To Ship Packages Within D Days is a medium binary search problem solved with the binary search on answer space pattern.
The best approach, optimal (binary search on the capacity), runs in O(n log S) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every capacity) up.
Problem
A conveyor belt holds packages that must be shipped in the given order; weights[i] is the weight of the i-th package. Each day the ship is loaded with the next packages from the belt, in order, as long as their total weight does not exceed the ship’s capacity.
Return the smallest ship capacity that lets you ship every package within days days.
Examples
Example 1
- Input
weights = [4, 8, 2, 6, 5, 3], days = 3- Output
12- Why
- Ship [4, 8], then [2, 6], then [5, 3] (loads 12, 8, 8). With capacity 11 the first day can only take [4], and the rest no longer fits into two more days.
Example 2
- Input
weights = [7, 2, 3], days = 3- Output
7- Why
- One package per day; the ship must still carry the heaviest package, 7.
Example 3
- Input
weights = [1, 1, 1, 1, 1], days = 1- Output
5- Why
- Everything goes on the first day, so the capacity is the total weight.
Constraints
1 <= days <= weights.length <= 5 * 10^41 <= weights[i] <= 500
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every capacity) | O(n · (S - M)) | O(1) |
| Optimal (binary search on the capacity) | O(n log S) | O(1) |
1Brute force (try every capacity)
O(n · (S - M))Up to S - M + 1 candidate capacities (S = total, M = max), each checked in O(n).O(1)A few counters.The capacity must be at least the heaviest package and never needs to exceed the total weight. Try each capacity from the smallest upward and return the first one whose greedy loading uses at most days days.
- lo = max(weights), hi = sum(weights).
- For c from lo to hi: if daysNeeded(c) <= days, return c.
- daysNeeded(c): load packages in order, starting a new day whenever the next one would push the load above c.
class Solution {
public int shipWithinDays(int[] weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) {
lo = Math.max(lo, w);
hi += w;
}
for (int c = lo; c < hi; c++) {
if (daysNeeded(weights, c) <= days) return c;
}
return hi;
}
private int daysNeeded(int[] weights, int cap) {
int used = 1, load = 0;
for (int w : weights) {
if (load + w > cap) {
used++;
load = 0;
}
load += w;
}
return used;
}
}class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
lo, hi = max(weights), sum(weights)
for c in range(lo, hi):
if self.daysNeeded(weights, c) <= days:
return c
return hi
def daysNeeded(self, weights: List[int], cap: int) -> int:
used, load = 1, 0
for w in weights:
if load + w > cap:
used += 1
load = 0
load += w
return usedclass Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) {
lo = max(lo, w);
hi += w;
}
for (int c = lo; c < hi; c++) {
if (daysNeeded(weights, c) <= days) return c;
}
return hi;
}
private:
int daysNeeded(const vector<int>& weights, int cap) {
int used = 1, load = 0;
for (int w : weights) {
if (load + w > cap) {
used++;
load = 0;
}
load += w;
}
return used;
}
};function shipWithinDays(weights, days) {
let lo = 0, hi = 0;
for (const w of weights) {
lo = Math.max(lo, w);
hi += w;
}
for (let c = lo; c < hi; c++) {
if (daysNeeded(weights, c) <= days) return c;
}
return hi;
}
function daysNeeded(weights, cap) {
let used = 1, load = 0;
for (const w of weights) {
if (load + w > cap) {
used++;
load = 0;
}
load += w;
}
return used;
}2Optimal (binary search on the capacity)
O(n log S)About log(S - M) rounds, each a linear greedy pass.O(1)A few counters.Feasibility is monotonic: if capacity c ships everything within days days, every larger capacity does too. Binary search the smallest feasible capacity in [max(weights), sum(weights)], testing each midpoint with the same greedy day count.
- lo = max(weights), hi = sum(weights).
- While lo < hi: mid = lo + (hi - lo) / 2; if daysNeeded(mid) <= days, hi = mid, else lo = mid + 1.
- Return lo.
class Solution {
public int shipWithinDays(int[] weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) {
lo = Math.max(lo, w);
hi += w;
}
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (daysNeeded(weights, mid) <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}
private int daysNeeded(int[] weights, int cap) {
int used = 1, load = 0;
for (int w : weights) {
if (load + w > cap) {
used++;
load = 0;
}
load += w;
}
return used;
}
}class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if self.daysNeeded(weights, mid) <= days:
hi = mid
else:
lo = mid + 1
return lo
def daysNeeded(self, weights: List[int], cap: int) -> int:
used, load = 1, 0
for w in weights:
if load + w > cap:
used += 1
load = 0
load += w
return usedclass Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) {
lo = max(lo, w);
hi += w;
}
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (daysNeeded(weights, mid) <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}
private:
int daysNeeded(const vector<int>& weights, int cap) {
int used = 1, load = 0;
for (int w : weights) {
if (load + w > cap) {
used++;
load = 0;
}
load += w;
}
return used;
}
};function shipWithinDays(weights, days) {
let lo = 0, hi = 0;
for (const w of weights) {
lo = Math.max(lo, w);
hi += w;
}
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (daysNeeded(weights, mid) <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}
function daysNeeded(weights, cap) {
let used = 1, load = 0;
for (const w of weights) {
if (load + w > cap) {
used++;
load = 0;
}
load += w;
}
return used;
}Edge cases to test
- days = 1: the answer is the total weight
- days = weights.length: the answer is the heaviest package
- One very heavy package among light ones (the lower bound is the maximum, not the average)
Hints
Hint 1
Packages must stay in order, so a given capacity defines a unique greedy loading: fill each day until the next package does not fit.
Hint 2
If capacity c works, so does any larger capacity. What does that monotonic property suggest?
Hint 3
Binary search the capacity between max(weights) and sum(weights), checking each candidate with the greedy day count.
FAQ
What is the best time complexity for Capacity To Ship Packages Within D Days?
Optimal (binary search on the capacity) runs in O(n log S) time and O(1) extra space. About log(S - M) rounds, each a linear greedy pass.
Which pattern does Capacity To Ship Packages Within D Days use?
It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.
Is there a brute force solution for Capacity To Ship Packages Within D Days?
Yes. Brute force (try every capacity) takes O(n · (S - M)) time and O(1) space. The capacity must be at least the heaviest package and never needs to exceed the total weight.
Which edge cases should I test for Capacity To Ship Packages Within D Days?
days = 1: the answer is the total weight; days = weights.length: the answer is the heaviest package; One very heavy package among light ones (the lower bound is the maximum, not the average).