Skip to content

Problem 6 — Capacity to Ship Packages

Problem 6 — Capacity to Ship Packages Within D Days

Section titled “Problem 6 — Capacity to Ship Packages Within D Days”

LeetCode 1011 | Difficulty: 🟡 Medium


A conveyor belt has packages that must be shipped within days days. The i-th package has weight weights[i]. Packages are loaded in order (you cannot reorder them).

Find the minimum weight capacity of the ship that can ship all packages within days days.

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation:
Day 1: 1+2+3+4+5 = 15
Day 2: 6+7 = 13
Day 3: 8 = 8
Day 4: 9 = 9
Day 5: 10 = 10

🧠 Pattern: Answer Space Search (Pattern 3)

Section titled “🧠 Pattern: Answer Space Search (Pattern 3)”

Answer space: Capacity ranges from max(weights) to sum(weights).

  • Min capacity: must carry the heaviest single package
  • Max capacity: carry all packages in one day

Monotonic property: If capacity C works, any larger capacity also works.


function shipWithinDays(weights, days) {
function canShip(capacity) {
let daysNeeded = 1;
let currentLoad = 0;
for (const w of weights) {
if (currentLoad + w > capacity) {
daysNeeded++;
currentLoad = 0;
}
currentLoad += w;
}
return daysNeeded <= days;
}
let lo = Math.max(...weights); // Must carry heaviest package
let hi = weights.reduce((a, b) => a + b, 0); // Carry all at once
let result = hi;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (canShip(mid)) {
result = mid; // Capacity works — try smaller
hi = mid - 1;
} else {
lo = mid + 1; // Capacity too small — try larger
}
}
return result;
}
console.log(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)); // 15
console.log(shipWithinDays([3,2,2,4,1,4], 3)); // 6
console.log(shipWithinDays([1,2,3,1,1], 4)); // 3

weights = [1,2,3,4,5,6,7,8,9,10], days = 5
lo = 10 (max weight)
hi = 55 (sum of all weights)
Step 1: mid=32 → canShip(32)=? days=1+1+1+1+1=5 ≤ 5 ✓ → result=32, hi=31
Step 2: mid=21 → canShip(21)=? days=1+1+1+1+1+1=6 > 5 ✗ → lo=22
Step 3: mid=26 → canShip(26)=? days=1+1+1+1+1=5 ≤ 5 ✓ → result=26, hi=25
Step 4: mid=23 → canShip(23)=? days=1+1+1+1+1+1=6 > 5 ✗ → lo=24
Step 5: mid=24 → canShip(24)=? days=1+1+1+1+1=5 ≤ 5 ✓ → result=24, hi=23
Result: 15 (after continuing search)... let me trace more carefully:
mid=15 → canShip(15)=?
Day 1: 1+2+3+4+5=15 days=1
Day 2: 6+7=13 days=2
Day 3: 8 days=3
Day 4: 9 days=4
Day 5: 10 days=5
5 ≤ 5 ✓ → result=15, hi=14
...answer converges to 15 ✓

MetricValue
TimeO(n × log(sum(weights)))
SpaceO(1)

  • Same pattern as Koko Bananas — just a different check function
  • Bounds: max(weights) to sum(weights)
  • Check function simulates packing days sequentially
  • This is the same underlying problem as Split Array Largest Sum (LeetCode 410)