BS on Answer — Capacity To Ship Packages Within D Days
↗ LeetCode: Capacity To Ship Packages Within D Days · Medium · pattern chapter →
Asked atAmazonGoogleMeta
Given package weights and days, find the minimum ship capacity that ships all in days days.
Example — weights=[1,2,3,4,5,6,7,8,9,10], days=5 → 15
Constraints — 1 ≤ days ≤ n ≤ 5·10⁴; 1 ≤ weights[i] ≤ 500.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Try every capacity
O(max·n). TLE.
Approach 2 — Binary search on capacity
Insight. feasible(cap) = can we ship in ≤ days days with this cap? Monotonic. Range: lo = max(weights) (must fit heaviest), hi = sum(weights).
java
int shipWithinDays(int[] w, int days) {
int lo = 0, hi = 0;
for (int x : w) { lo = Math.max(lo, x); hi += x; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int used = 1, load = 0;
for (int x : w) {
if (load + x > mid) { used++; load = 0; }
load += x;
}
if (used <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}Execution Trace
Step 1 / 6cap 32 fits in 2 days
Complexity — Time O(n log sum); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Linear scan on cap | O(max · n) | O(1) |
| BS on answer | O(n log sum) | O(1) |
When to use which
- "Min feasible X with monotone predicate" → BS on answer.
- Return the split itself → after BS converges, re-simulate to record boundaries.
- Very large sums → use
longfor hi bound.
AI Study CompanionBeta
Related problems
- Koko Eating Bananas
- Split Array Largest Sum — same skeleton
- Divide Chocolate — maximise the minimum
Was this page helpful?
📚 Related problems