67. Capacity To Ship Packages Within D Days
🔗 LeetCode Problem: 1011. Capacity To Ship Packages Within D Days
📊 Difficulty: Medium
🏷️ Topics: Array, Binary Search
Problem Statement
A conveyor belt has packages that must be shipped from one port to another within days days.
The i-th 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, 2
2nd day: 3
3rd day: 1
4th day: 1
Constraints:
- 1 <= days <= weights.length <= 5 * 10^4
- 1 <= weights[i] <= 500
🎨 Visual Understanding
The Problem Visualized
Example 1: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
If capacity = 15:
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 ✓
Total: 5 days ✓
If capacity = 14:
Day 1: [1,2,3,4,5] = 15 ✗ Can't fit! Exceeds 14!
OR
Day 1: [1,2,3,4] = 10 ✓
Day 2: [5,6] = 11 ✓
Day 3: [7] = 7 ✓
Day 4: [8] = 8 ✓
Day 5: [9] = 9 ✓
Day 6: [10] = 10 ✓
Total: 6 days ✗ Exceeds 5 days!
Minimum capacity = 15
Example 2: weights = [3,2,2,4,1,4], days = 3
If capacity = 6:
Day 1: [3,2] = 5 ✓
Day 2: [2,4] = 6 ✓
Day 3: [1,4] = 5 ✓
Total: 3 days ✓
If capacity = 5:
Day 1: [3,2] = 5 ✓
Day 2: [2] = 2 ✓ (can't add 4, would exceed 5)
Day 3: [4] = 4 ✓
Day 4: [1,4] = 5 ✓
Total: 4 days ✗ Exceeds 3 days!
Minimum capacity = 6
Visual representation of shipping process:
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], capacity = 15
Day 1: Load until full
1 → total = 1
2 → total = 3
3 → total = 6
4 → total = 10
5 → total = 15 ✓ Ship leaves!
Day 2: Continue from next package
6 → total = 6
7 → total = 13 ✓ Ship leaves!
Day 3: 8 ✓
Day 4: 9 ✓
Day 5: 10 ✓
All shipped in 5 days!
🚨 CRITICAL INSIGHT - Binary Search on Answer Space!
The Key Pattern!
This is IDENTICAL to "Koko Eating Bananas"!
Both are "Binary Search on Answer" problems!
What are we searching?
NOT searching in the array
Searching for OPTIMAL CAPACITY value
Search Space:
Minimum capacity: max(weights) (must carry heaviest package)
Maximum capacity: sum(weights) (carry everything in 1 day)
Range: [max(weights), sum(weights)]
Key Property (Monotonic):
If capacity C works (ships in ≤ days):
→ Any C' > C also works (larger capacity)
If capacity C doesn't work:
→ Any C' < C also doesn't work (smaller capacity)
Pattern: [NO NO NO NO | YES YES YES YES]
[too small | large enough ]
↑
Find this boundary!
We want: MINIMUM capacity that works
= Find FIRST "YES"
= Binary search for leftmost valid!
How to Check if Capacity Works
For a given capacity C, can we ship in ≤ days?
Greedy simulation:
currentLoad = 0
daysUsed = 1
For each package:
If currentLoad + weight > C:
Ship current load (end this day)
daysUsed++
currentLoad = weight
Else:
currentLoad += weight
If daysUsed <= days: capacity works! ✓
Else: capacity too small ✗
Example: weights = [1,2,3,4,5,6,7,8,9,10], C = 15, days = 5
Day 1: 1+2+3+4+5 = 15 (can't add 6)
Day 2: 6+7 = 13 (can't add 8)
Day 3: 8
Day 4: 9
Day 5: 10
Total days = 5 ≤ 5 ✓ Works!
Why Binary Search Works
Example: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Search space: C ∈ [10, 55]
min = max(weights) = 10
max = sum(weights) = 55
Test different capacities:
C = 10: Takes 10 days ✗
C = 11: Takes 9 days ✗
C = 12: Takes 8 days ✗
C = 13: Takes 7 days ✗
C = 14: Takes 6 days ✗
C = 15: Takes 5 days ✓
C = 16: Takes 5 days ✓
...
C = 55: Takes 1 day ✓
Pattern: [✗ ✗ ✗ ✗ ✗ | ✓ ✓ ✓ ...]
[10...14 | 15...55 ]
↑
Find this first YES!
Binary search finds the boundary efficiently!
🎯 Approach 1: Linear Search (Brute Force)
The Most Natural Thinking 💭
Core Logic:
Try each capacity from max(weights) to sum(weights):
Check if capacity C allows shipping in ≤ days
Return first C that works
Implementation
public int shipWithinDays(int[] weights, int days) {
// Find bounds
int minCapacity = 0;
int maxCapacity = 0;
for (int weight : weights) {
minCapacity = Math.max(minCapacity, weight);
maxCapacity += weight;
}
// Try each capacity
for (int capacity = minCapacity; capacity <= maxCapacity; capacity++) {
if (canShip(weights, days, capacity)) {
return capacity;
}
}
return maxCapacity;
}
private boolean canShip(int[] weights, int days, int capacity) {
int daysNeeded = 1;
int currentLoad = 0;
for (int weight : weights) {
if (currentLoad + weight > capacity) {
daysNeeded++;
currentLoad = weight;
} else {
currentLoad += weight;
}
}
return daysNeeded <= days;
}
⏰ Time: O(n × sum(weights)) - Try each capacity, check each package
💾 Space: O(1) - Only variables
❌ Problem: Too slow! sum(weights) can be 25,000,000!
🎯 Approach 2: Binary Search on Answer (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Search space: [max(weights), sum(weights)]
Property: Monotonic (if C works, C+1 works)
Goal: Find MINIMUM C that works
Perfect for binary search!
The Strategy:
Binary Search on Capacity C:
1. left = max(weights), right = sum(weights)
2. While left < right:
a. mid = left + (right - left) / 2
b. If canShip(weights, days, mid):
mid works, try smaller
right = mid
c. Else:
mid too small, need larger
left = mid + 1
3. Return left
Implementation
public int shipWithinDays(int[] weights, int days) {
// Find search bounds
int left = 0; // Minimum capacity (largest package)
int right = 0; // Maximum capacity (all packages in 1 day)
for (int weight : weights) {
left = Math.max(left, weight); // Must carry heaviest package
right += weight; // Sum of all weights
}
// Binary search for minimum valid capacity
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) {
// This capacity works, try smaller
right = mid;
} else {
// This capacity too small, need larger
left = mid + 1;
}
}
return left;
}
// Check if given capacity can ship all packages within days
private boolean canShip(int[] weights, int days, int capacity) {
int daysNeeded = 1;
int currentLoad = 0;
for (int weight : weights) {
// Can we add this package to current ship load?
if (currentLoad + weight > capacity) {
// No, ship current load and start new day
daysNeeded++;
currentLoad = weight;
// Early termination
if (daysNeeded > days) {
return false;
}
} else {
// Yes, add to current load
currentLoad += weight;
}
}
return daysNeeded <= days;
}
⏰ Time: O(n × log(sum(weights))) - Binary search × checking all packages
💾 Space: O(1) - Only variables
🔍 Dry Run
Example 1: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Goal: Find minimum capacity
Find bounds:
left = max(weights) = 10
right = sum(weights) = 55
Initial: left = 10, right = 55
Iteration 1:
mid = 10 + (55 - 10) / 2 = 32
Can ship with capacity 32?
Day 1: 1+2+3+4+5+6+7 = 28
Day 2: 8+9 = 17
Day 3: 10
Total: 3 days ≤ 5 ✓
Works! Try smaller
right = 32
Range: [10, 32]
Iteration 2:
mid = 10 + (32 - 10) / 2 = 21
Can ship with capacity 21?
Day 1: 1+2+3+4+5+6 = 21
Day 2: 7+8 = 15
Day 3: 9
Day 4: 10
Total: 4 days ≤ 5 ✓
Works! Try smaller
right = 21
Range: [10, 21]
Iteration 3:
mid = 10 + (21 - 10) / 2 = 15
Can ship with capacity 15?
Day 1: 1+2+3+4+5 = 15
Day 2: 6+7 = 13
Day 3: 8
Day 4: 9
Day 5: 10
Total: 5 days ≤ 5 ✓
Works! Try smaller
right = 15
Range: [10, 15]
Iteration 4:
mid = 10 + (15 - 10) / 2 = 12
Can ship with capacity 12?
Day 1: 1+2+3+4 = 10
Day 2: 5+6 = 11
Day 3: 7
Day 4: 8
Day 5: 9
Day 6: 10
Total: 6 days > 5 ✗
Too small! Need larger
left = 13
Range: [13, 15]
Iteration 5:
mid = 13 + (15 - 13) / 2 = 14
Can ship with capacity 14?
Day 1: 1+2+3+4 = 10
Day 2: 5+6 = 11
Day 3: 7
Day 4: 8
Day 5: 9
Day 6: 10
Total: 6 days > 5 ✗
Too small! Need larger
left = 15
Range: [15, 15]
Loop ends (left == right)
return 15 ✓
Example 2: weights = [3,2,2,4,1,4], days = 3
Bounds:
left = 4, right = 16
Initial: left = 4, right = 16
Iteration 1:
mid = 10
Can ship with 10?
Day 1: 3+2+2 = 7
Day 2: 4+1+4 = 9
Total: 2 days ≤ 3 ✓
right = 10
Iteration 2:
mid = 7
Can ship with 7?
Day 1: 3+2+2 = 7
Day 2: 4+1 = 5
Day 3: 4
Total: 3 days ≤ 3 ✓
right = 7
Iteration 3:
mid = 5
Can ship with 5?
Day 1: 3+2 = 5
Day 2: 2 (can't add 4)
Day 3: 4+1 = 5
Day 4: 4
Total: 4 days > 3 ✗
left = 6
Iteration 4:
mid = 6
Can ship with 6?
Day 1: 3+2 = 5
Day 2: 2+4 = 6
Day 3: 1+4 = 5
Total: 3 days ≤ 3 ✓
right = 6
Loop ends
return 6 ✓
🎯 Why This Works - Deep Dive
The Greedy Simulation:
═══════════════════════════════════════════════════════════════
To check if capacity C works:
Load packages greedily in order
When next package doesn't fit, ship and start new day
Why greedy works?
We MUST ship in order (constraint)
Best strategy: fit as many as possible each day
This minimizes days used
The Monotonic Property:
═══════════════════════════════════════════════════════════════
If capacity C allows shipping in D days:
→ Any C' > C also allows shipping in ≤ D days
(More capacity = fewer or same days)
If capacity C requires > D days:
→ Any C' < C requires ≥ D days
(Less capacity = more or same days)
This creates sorted pattern:
[TOO SMALL ... | LARGE ENOUGH ...]
↑
Find boundary
The Search Bounds:
═══════════════════════════════════════════════════════════════
Minimum capacity:
Must carry heaviest single package
left = max(weights)
Maximum capacity:
Carry everything in 1 day
right = sum(weights)
Tighter than [1, infinity]!
The "Find First Valid" Pattern:
═══════════════════════════════════════════════════════════════
Loop: while (left < right)
Converge to minimum valid
When valid: right = mid
mid works, but try smaller
Keep mid in range
When invalid: left = mid + 1
mid doesn't work, exclude it
Return: left (minimum valid capacity)
Same pattern as "Koko Eating Bananas"!
Time Complexity:
═══════════════════════════════════════════════════════════════
Binary search: O(log(sum - max))
≈ O(log(sum(weights)))
Each check: O(n) to process all packages
Total: O(n × log(sum(weights)))
Much better than O(n × sum(weights))!
Space: O(1) - only variables
The Greedy Strategy Proof
Claim: Greedy loading minimizes days needed
Proof by contradiction:
Suppose greedy uses D days
Suppose optimal uses D' < D days
There must be a day k where:
Greedy ships package P starting day k+1
Optimal includes P in day k
But greedy ONLY ships when:
currentLoad + weight[P] > capacity
So optimal must be exceeding capacity! ✗
Contradiction!
Therefore: Greedy is optimal ✓
⚠️ Common Mistakes to Avoid
Mistake 1: Wrong bounds
// ❌ WRONG - Should be max, not min
int left = 1;
// ❌ WRONG - Might be too large
int right = Integer.MAX_VALUE;
// ✓ CORRECT
int left = max(weights); // Must carry heaviest
int right = sum(weights); // Maximum useful capacity
Mistake 2: Not handling edge case
// ❌ WRONG - What if single package > capacity?
if (weight > capacity) {
// This should never happen with correct bounds!
}
// ✓ CORRECT - Bounds ensure capacity >= max(weights)
left = Math.max(left, weight);
Mistake 3: Wrong loop condition
// ❌ WRONG
while (left <= right) {
if (canShip(weights, days, mid)) {
right = mid; // Might cause infinite loop!
}
}
// ✓ CORRECT
while (left < right) {
if (canShip(weights, days, mid)) {
right = mid;
}
}
Mistake 4: Not starting with daysNeeded = 1
// ❌ WRONG
int daysNeeded = 0;
for (int weight : weights) {
currentLoad += weight;
if (currentLoad > capacity) {
daysNeeded++; // First package uses day 0?
}
}
// ✓ CORRECT
int daysNeeded = 1; // First package uses day 1!
Mistake 5: Forgetting order constraint
// ❌ WRONG - Sorting destroys order!
Arrays.sort(weights);
// ✓ CORRECT - Must process in given order
// No sorting allowed!
🎯 Pattern Recognition
Problem Type: Binary Search on Answer Space
Core Pattern: Find Minimum Capacity with Constraint
When to Apply:
✓ Need to find OPTIMAL value (not in array)
✓ Can CHECK if value satisfies constraint
✓ Monotonic property exists
✓ Range of possible values known
✓ Checking is faster than trying all
Recognition Keywords:
- "Minimum capacity"
- "Within D days/hours"
- "Ship packages"
- "In order"
- Optimization with constraint
Similar Problems:
- Koko Eating Bananas (LC 875) - IDENTICAL pattern!
- Split Array Largest Sum (LC 410)
- Minimize Max Distance to Gas Station (LC 774)
- Magnetic Force Between Balls (LC 1552)
Key Pattern Elements:
┌────────────────────────────────────────────┐
│ Binary Search on Answer: │
│ 1. Define search space [min, max] │
│ 2. Write check function (can achieve?) │
│ 3. Binary search for boundary │
│ 4. Return optimal value │
│ │
│ Greedy simulation: │
│ Load packages in order │
│ Ship when next doesn't fit │
└────────────────────────────────────────────┘
This is THE classic capacity/rate optimization pattern!
🧠 Interview Strategy
Step 1: "Find minimum capacity → Binary search on answer"
Step 2: "Search space: [max(weights), sum(weights)]"
Step 3: "Check function: simulate greedy loading"
Step 4: "Monotonic: larger capacity → fewer days"
Step 5: "Find first valid capacity"
Key Points to Mention:
- Binary search on CAPACITY (not array)
- Bounds: max(weights) to sum(weights)
- Check: greedy simulation in order
- Greedy: fit as many as possible per day
- Monotonic property
- Find minimum valid capacity
- Loop: while (left < right)
- When valid: right = mid
- When invalid: left = mid + 1
- Time: O(n log(sum))
Why This Approach?
"This is a binary search on answer space problem. I'm searching
for the optimal capacity value in the range [max(weights),
sum(weights)]. The key insight is the monotonic property: if
capacity C works, any larger capacity also works. For each
candidate capacity, I simulate greedy loading - packing as many
packages as possible per day in the given order. If the days
needed is within the limit, I try a smaller capacity. Otherwise,
I need a larger capacity. This gives O(n log(sum)) time."
Why Greedy?
"I must ship packages in order, so the best strategy is to fit
as many as possible in each day. This minimizes the number of
days used. Any other strategy would use more or the same number
of days."
Why These Bounds?
"The minimum capacity must be at least max(weights) - we need
to carry the heaviest package. The maximum useful capacity is
sum(weights) - carrying everything in one day. Going larger
doesn't help since we're already at 1 day."
📝 Quick Revision Notes
🎯 Core Concept:
Ship Packages in D Days: Find minimum capacity. Binary search on answer space [max(weights), sum(weights)]. Check with greedy simulation: load in order, ship when next doesn't fit. Monotonic: larger capacity → fewer days. Find first valid. Loop: left < right!
⚡ Quick Implementation:
class Test {
public int shipWithinDays(int[] a, int k) {
int left = Integer.MIN_VALUE; // max of all numbers of array.
int right = 0; // sum of all numbers of array.
for(int num : a) {
left = Math.max(left, num);
right += num;
}
// same template
while (left < right) {
int mid = left + (right - left) / 2;
// check if with this 'mid' capacity, can we ship within k days.
if(canShip(a, k, mid)) {
// we got the result. But, check for better still.
// We need to reduce ship capacity and hence reduce right.
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canShip(int[] a, int k, int capacity) {
int currentWeight = 0;
int daysNeeded = 1; // days needed with this 'capacity' ship
for(int num : a) {
// can we include current weight?
if(currentWeight + num > capacity) {
// NO. Include it in next day and increment the days taken.
currentWeight = num;
daysNeeded++;
} else {
currentWeight += num;
}
}
return daysNeeded <= k; // can ship
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(t.shipWithinDays(new int[] {1,2,3,4,5,6,7,8,9,10}, 5) == 15);
System.out.println(t.shipWithinDays(new int[] {3,2,2,4,1,4}, 3) == 6);
System.out.println(t.shipWithinDays(new int[] {1,2,3,1,1}, 4) == 3);
System.out.println(t.shipWithinDays(new int[] {10}, 1) == 10);
System.out.println(t.shipWithinDays(new int[] {1,2,3,4,5}, 5) == 5);
System.out.println(t.shipWithinDays(new int[] {1,2,3,4,5}, 1) == 15);
System.out.println(t.shipWithinDays(new int[] {5,5,5,5}, 2) == 10);
System.out.println(t.shipWithinDays(new int[] {1,2,3,10}, 2) == 10);
}
}
🔑 Key Insights:
- Pattern: Binary Search on Answer (Capacity)
- Bounds: [max(weights), sum(weights)]
- Check: Greedy simulation in order
- Greedy: Fit max packages per day
- Monotonic: C works → C+1 works
- Find: Minimum valid capacity
- Loop:
while (left < right) - Valid:
right = mid(try smaller) - Invalid:
left = mid + 1(need larger) - Time: O(n × log(sum)), Space: O(1)
🎪 Memory Aid:
"Binary search on capacity! Greedy load, ship when full!"
Think: "Same as Koko bananas - find minimum rate!"
💡 The Key Insight:
NOT searching IN array
Searching FOR optimal capacity
Monotonic property:
Capacity C works → C+1 works
Capacity C fails → C-1 fails
[FAIL FAIL | PASS PASS PASS]
↑
Find boundary!
⚠️ Critical Details:
1. Bounds: left = max(weights), right = sum(weights)
2. Greedy: Load in order until exceeds capacity
3. Ship: Start new day when next doesn't fit
4. daysNeeded starts at 1 (not 0!)
5. Valid: right = mid (try smaller)
6. Invalid: left = mid + 1
7. Return: left (minimum capacity)
🔥 The Greedy Simulation:
capacity = 15, weights = [1,2,3,4,5,6,7,8,9,10]
currentLoad = 0, daysNeeded = 1
Process each:
1: 0+1=1 ≤ 15, add
2: 1+2=3 ≤ 15, add
3: 3+3=6 ≤ 15, add
4: 6+4=10 ≤ 15, add
5: 10+5=15 ≤ 15, add
6: 15+6=21 > 15, ship! daysNeeded=2, load=6
7: 6+7=13 ≤ 15, add
8: 13+8=21 > 15, ship! daysNeeded=3, load=8
9: 8+9=17 > 15, ship! daysNeeded=4, load=9
10: 9+10=19 > 15, ship! daysNeeded=5, load=10
Total: 5 days ✓
💡 Why Greedy Works:
Must ship in ORDER (constraint)
Best strategy: Maximize load per day
This minimizes days used
Any other strategy wastes capacity!
🧪 Edge Cases
Case 1: Single package
Input: weights = [10], days = 1
Output: 10
(Must carry it)
Case 2: Days equals packages
Input: weights = [1,2,3,4,5], days = 5
Output: 5
(One package per day, need capacity for largest)
Case 3: Ship all in one day
Input: weights = [1,2,3,4,5], days = 1
Output: 15
(Carry everything)
Case 4: All same weight
Input: weights = [5,5,5,5], days = 2
Output: 10
(Two packages per day)
Case 5: Large last package
Input: weights = [1,2,3,10], days = 2
Output: 11
(Must carry the 10, can combine with 1)
All handled correctly! ✓
Related Patterns
- Koko Eating Bananas (LC 875) - IDENTICAL pattern
- Split Array Largest Sum (LC 410) - Same approach
- Minimize Max Distance to Gas Station (LC 774)
Happy practicing! 🎯
Note: This is virtually IDENTICAL to Koko Eating Bananas! Master this "binary search on answer + greedy simulation" pattern - it appears frequently in MAANG interviews!