#1011 Capacity To Ship Packages Within D Days
the problem
In plain words
Packages must ship in the given order. Each day the ship is loaded with consecutive packages up to its capacity. Return the least capacity that ships everything within days days.
in weights = [1,2,3,4,5,6,7,8,9,10], days = 5
out 15
[1..5] [6,7] [8] [9] [10].
in weights = [3,2,2,4,1,4], days = 3
out 6
in weights = [1,2,3,1,1], days = 4
out 3
- 1 ≤ days ≤ weights.length ≤ 5·10⁴
- 1 ≤ weights[i] ≤ 500
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBinary search on the answer
Capacity lies between max(weights) (must fit the heaviest box) and sum(weights) (one day). Bigger capacity never needs more days — monotonic, so binary search it.
solutions
From brute force to optimal
Start at the heaviest box and increase until the greedy loading fits in days.
- cap = max(weights).
- While daysNeeded(cap) > days: cap++.
- Return cap.
Up to S = sum of weights capacities, each simulated in O(n).
Counters only.
class Solution { public int shipWithinDays(int[] weights, int days) { int cap = 0; for (int w : weights) cap = Math.max(cap, w); // must at least fit the heaviest box while (daysNeeded(weights, cap) > days) cap++; return cap; } static int daysNeeded(int[] weights, int cap) { int used = 1, load = 0; for (int w : weights) { if (load + w > cap) { // this box goes on tomorrow's ship used++; load = 0; } load += w; } return used; }}Search [max, sum] for the first capacity whose greedy loading needs ≤ days.
- lo = max(weights), hi = sum(weights).
- daysNeeded(mid) ≤ days → hi = mid.
- Else lo = mid + 1.
log S guesses (≈ 25 for S = 2.5·10⁷), each O(n).
Counters only.
class Solution { public int shipWithinDays(int[] weights, int days) { int lo = 0, hi = 0; for (int w : weights) { lo = Math.max(lo, w); // smallest possible capacity hi += w; // ship everything in one day } while (lo < hi) { int mid = lo + (hi - lo) / 2; if (daysNeeded(weights, mid) <= days) hi = mid; // works: try smaller else lo = mid + 1; // too small: need more capacity } return lo; } private int daysNeeded(int[] weights, int cap) { int used = 1, load = 0; for (int w : weights) { if (load + w > cap) { used++; load = 0; } load += w; } return used; }}in the room
How to say it in the interview
talk track
- Justify the greedy check: filling each day as much as possible never uses more days than any other loading.
- Point out it's the same shape as Koko — interviewers like hearing you recognise the family.
traps
- Starting lo at 1 instead of max(weights): a capacity smaller than one box makes the check meaningless.
what they ask next
Follow-ups
Split Array Largest Sum (LC 410)?
Identical: minimise the largest subarray sum with k parts — binary search the sum, greedy count of parts.
before you submit
Edge cases to test
- days = 1 → the sum of all weights.
- days = number of packages → the heaviest single package.
- One heavy package in the middle decides the answer: [1, 1, 500, 1, 1] in 2 days → 502.
practise next
Similar problems
- #875Koko Eating BananasMediumin Binary Search
- #778Swim in Rising WaterHardin Shortest Paths