1. Min capacity
Capacity must at least hold the heaviest single package.
let lo = Math.max(...weights)Typorithm · medium
Ship Within Days
ship-within-daysbinary-search-answeranswer-spacefeasibilityordered-load
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Ship Within Days
Binary Search on Answer
Binary search the ship capacity; greedily pack in order counting days, and minimize the capacity that fits within days.
Capacity ranges from the heaviest package (must fit) to the total weight (one day).
For a candidate capacity, greedily load packages in order, starting a new day whenever the next would overflow.
If the days used fit the budget, search a smaller capacity; otherwise search larger.
01
lo = max weight, hi = total weight.
02
Greedily pack in given order.
03
Minimize capacity within days.
function shipWithinDays(weights, days) {
let lo = Math.max(...weights);
let hi = weights.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = (lo + hi) >> 1;
let need = 1;
let load = 0;
for (const w of weights) {
if (load + w > mid) {
need += 1;
load = 0;
}
load += w;
}
if (need <= days) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Max capacity
One day fits everything if capacity is the total weight.
let hi = weights.reduce((a, b) => a + b, 0)3. Start a new day
Overflowing the capacity opens a new shipping day.
if (load + w > mid) {
need += 1;
load = 0;
}4. Fits in days
If it ships within the day budget, try a smaller capacity.
if (need <= days) {
hi = mid;
}A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.