Coding Interview PatternsCapacity To Ship Packages Within D Days
MediumModified Binary Search
Capacity To Ship Packages Within D Days
Explanation & Solution
Description
A conveyor belt has packages that must be shipped from one port to another within days days.
The i-th package has a weight of weights[i]. Each day, we load packages onto the ship in the order given. 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 being shipped within days days.
Input:weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
Output: 15
Explanation: A capacity of 15 ships packages in 5 days: [1,2,3,4,5], [6,7], [8], [9], [10].
Constraints
1 <= days <= weights.length <= 5 * 10^41 <= weights[i] <= 500
Approach
Modified Binary Search pattern
1. Define the Search Space
- Minimum capacity:
max(weights)— must be able to carry the heaviest single package. - Maximum capacity:
sum(weights)— ship everything in one day.
2. Binary Search on Capacity
- For candidate capacity
mid, simulate loading packages greedily: keep adding to the current day until adding the next package would exceedmid, then start a new day.
3. Check Feasibility
- Count the number of days needed. If
daysNeeded <= days, the capacity works → try smaller:hi = mid. - Otherwise, capacity too small:
lo = mid + 1.
4. Return the Minimum Capacity
- When
lo === hi, return the answer.
🧠 Key Insight
- This is a binary search on the answer problem. The feasibility function is monotonic: larger capacity always requires fewer or equal days.
Time
O(n · log(sum - max)) — binary search with linear feasibility check.Space
O(1).Visualization
Input:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
—
Press ▶ or use ← → to step through
Pointer iPointer jProcessedDone
58 steps