Ship Packages Within D Days

Hardbinary search on answerBinary search on the answerbinary-searchgreedybinary-search-on-answer

Maintained by Vikas Dulgunde, 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

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5

Output: 15

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.

Input: weights = [3,2,2,4,1,4], days = 3

Output: 6

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.

Input: weights = [1,2,3,1,1], days = 4

Output: 3

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.

Loading the editor...

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?

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5

Output: 15

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.

Input: weights = [3,2,2,4,1,4], days = 3

Output: 6

Input: weights = [1,2,3,1,1], days = 4

Output: 3

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

Hint 3

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?

Ship Packages Within D Days

Examples

Constraints

Hints

Approaches

Linear scan over capacities

Binary search on the answer

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Ship Packages Within D Days

Examples

Constraints

Hints

Approaches

Linear scan over capacities

Binary search on the answer

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep