Ship Packages Within D Days
Maintained by Vikas D, software engineer
Packages sit on a conveyor belt with fixed weights, and they must be loaded onto the ship in exactly that order. Each day the ship picks up a contiguous run of the next packages, as long as their combined weight stays within the ship's capacity. You cannot reorder packages and you cannot split one package between two days.
You are given a target number of days. A larger ship can carry more per day and finish in fewer days; a smaller ship needs more days. Your job is to find the smallest capacity that still gets everything shipped on time.
The answer is bounded on both sides. Capacity can never be less than the heaviest single package, because that one package must fit in a day on its own. Capacity never needs to exceed the total weight, because that would let the whole belt ship in a single day. The minimum valid capacity lives somewhere in that range.
Examples
Capacity 15 supports a 5-day plan: [1,2,3,4,5]=15, [6,7]=13, [8]=8, [9]=9, [10]=10. Any capacity below 15 forces a sixth day, so 15 is the minimum.
Capacity 6 supports a 3-day plan: [3,2]=5, [2,4]=6, [1,4]=5, which loads every package in order across exactly 3 days. Capacity 5 cannot fit [2,4] together and ends up needing a fourth day, so 6 is the minimum.
Capacity 3 gives [1,2]=3, [3]=3, [1,1]=2, which is only three days, so there is slack to spare. The heaviest package is 3, so capacity can never drop below 3, and 3 already finishes within 4 days, making it the answer.
Constraints
- 1 <= days <= weights.length <= 5 * 10^4
- 1 <= weights[i] <= 500
- Packages must be shipped in the given order and never split across days
- The answer always exists because days never exceeds the number of packages
Visible test cases
- shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5) == 15
- shipWithinDays([3,2,2,4,1,4], 3) == 6
- shipWithinDays([1,2,3,1,1], 4) == 3
- shipWithinDays([10], 1) == 10
- shipWithinDays([1,1,1,1,1], 5) == 1
- shipWithinDays([5,5,5,5], 2) == 10
Hints
Hint 1
If someone hands you a candidate capacity, can you quickly decide whether it is enough? Greedily fill each day until the next package would overflow, then start a new day, and count the days.
Hint 2
Notice the days needed is monotonic in capacity: as capacity grows, the day count only ever decreases or stays the same. That monotonic boolean (does this capacity finish in time?) is exactly what binary search needs.
Hint 3
Search the capacity range. The low bound is the maximum single weight (it must fit alone); the high bound is the total of all weights (one day for everything). Binary search for the smallest capacity that passes the feasibility check.
Approaches
Linear scan over capacities
Time O(n * S) where S is the total weight, since the answer can be as large as the sum and each check scans all n packages · Space O(1)Try every capacity starting from the heaviest package and moving up, returning the first one that ships within the day limit.
- Set the candidate capacity to the maximum single weight.
- For each candidate, simulate loading: greedily add packages to the current day until the next one overflows, then increment the day count and reset the day load.
- If the simulated day count is at most days, return that capacity.
- Otherwise increase the candidate by one and repeat.
Binary search on the answer
Time O(n * log(S)) where S is the total weight, n package scans per feasibility check across log(S) iterations · Space O(1)The feasibility test (does capacity C finish within days days?) is monotonic, so binary search the capacity range instead of scanning it linearly.
- Set lo to the maximum single weight and hi to the sum of all weights.
- Write a helper that, for a given capacity, greedily packs packages day by day and returns how many days it needs.
- While lo < hi, take mid in the middle. If the helper needs at most days days, the capacity might be wastefully large, so move hi to mid. Otherwise it is too small, so move lo to mid + 1.
- When lo equals hi the loop has converged on the smallest feasible capacity; return it.
Common mistakes
- Setting the low bound to 1 or 0 instead of the maximum weight: any capacity below the heaviest package can never ship it, so the feasibility check would loop forever or never terminate cleanly.
- Starting the day counter at 0 instead of 1: the first day is in use the moment you place the first package, so an off-by-one here under-counts days and reports an undersized capacity as valid.
- Using load + w >= cap rather than > cap: a package whose weight exactly fills the remaining room should still fit on the current day, so the comparison must be strictly greater than.
- Returning mid at the end instead of lo: once the search converges, lo is the boundary; grabbing the last mid can land one step off the true minimum.
- Counting items per day instead of summing weights: the constraint is total weight per day against capacity, not a fixed package count.
Follow-up variations
- Return the actual day-by-day grouping, not just the minimum capacity.
- Allow each day to also have a maximum package count in addition to the weight cap, and find the smallest capacity under both limits.
- Generalize to splitting an array into at most k contiguous parts while minimizing the largest part sum, which is the same problem dressed differently.
- If packages could be reordered freely, how would the optimal capacity change, and what makes that variant harder?