← DSA Atlas
Dedicated problem page · #1011

Capacity to Ship Packages Within D Days

MediumBinary SearchBinary search on capacity with a greedy feasibility checkBinary search on the answer
Solve on LeetCode ↗
1011
MediumBinary SearchBinary search on the answerBinary search on capacity with a greedy feasibility check

Capacity to Ship Packages Within D Days

A conveyor belt has packages that must be shipped within days days. The i-th package has weight weights[i]. Each day you load packages onto the ship in the given order without exceeding the ship's maximum weight capacity. Return the least weight capacity of the ship that lets all packages be shipped within days days.

Open official problem prompt ↗
In plain English

Find the smallest ship capacity that still delivers every package, in order, within the day limit.

Picture it like this

Packing moving boxes of a fixed size across a set number of days: a bigger box lets you finish sooner, so you shrink the box size to the smallest that still finishes on schedule.

Example
Input
weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output
15
Why
With capacity 15 the greedy loads are (1,2,3,4,5)=15, (6,7)=13, (8), (9), (10) - exactly 5 days. Any smaller capacity forces a sixth day, so 15 is the minimum.
Constraints
1 <= days <= weights.length <= 5*10^41 <= weights[i] <= 500Packages must be shipped in their given orderEach day's total load cannot exceed the ship capacity
Pattern lesson

See the pattern, then code

Binary search on capacity with a greedy feasibility check
Recognition clue

You minimize a capacity subject to a day limit, and checking whether a given capacity fits within the day budget is a simple linear scan - the hallmark of binary search on the answer.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. If capacity C works within the day limit, any capacity larger than C also works, so feasibility is monotone in C. The minimum valid capacity is at least the heaviest single package (it must fit in one day) and at most the total weight (ship everything in one day).

New words, made simpleKnow these before the algorithm
Binary search on the answer
Searching over candidate capacities and testing each for feasibility rather than searching array positions.
Greedy feasibility check
For a fixed capacity, loading as much as fits each day - provably the day-minimizing strategy.
Monotone feasibility
Once a capacity is enough, every larger capacity is also enough.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force capacity scan

Correct but the capacity range can be tens of thousands, making it far too slow.

Try every capacity from max(weights) upward until one fits within days.

Time O(n * (sum - max))Space O(1)
Best choiceBinary search on capacity

Logarithmic number of feasibility checks, each linear - fast and clean.

Bound capacity by [max, sum] and binary search, using a greedy day count as the test.

Time O(n log(sum - max))Space O(1)
The rule we keep true

Invariant

Throughout the search, hi is a capacity known to ship within days days and lo-1 is known to be insufficient, so the answer lies in [lo, hi].

Why this is correct

Reasoning

For a fixed capacity, greedily starting a new day only when the next package would overflow uses the fewest possible days, so the count it returns is exact. Larger capacities never need more days, making the 'days needed <= days' predicate monotone. Binary search over the capacity range then finds the exact threshold where the predicate flips from false to true, which is the minimum feasible capacity. The lower bound max(weights) guarantees every package fits in some day; the upper bound sum(weights) trivially ships everything in one day.

The algorithm in three movesSay these aloud before coding
1Set lo = max(weights) and hi = sum(weights) as capacity bounds

lo=10 (max), hi=55 (sum)

2For a candidate capacity, greedily fill days: start a new day when the next package would overflow

mid=32 needs 2 days <=5 -> hi=32

3Count days needed for that capacity

converges: mid=15 needs 5 days <=5 -> hi=15; mid=14 needs 6 days -> lo=15

4If days needed <= days, the capacity is feasible so shrink hi = mid; else lo = mid+1

5Return lo, the smallest feasible capacity

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
43
54
65
76
87
98
109
1 · Readweights, days=5
2 · AskWhat capacities are possible?
3 · Update statelo=10, hi=55
4 · ResultAnswer somewhere in [10,55]
Key takeaway

Capacity is searched between the heaviest package (10) and the total load (55), settling on 15.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-9Day counter

    Greedily accumulate weight; when the next package would overflow cap, open a new day and reset the running load.

  2. 2
    Lines 10Search bounds

    Capacity must be at least the heaviest package and need not exceed the total weight.

  3. 3
    Lines 11-16Lower-bound binary search

    When a capacity is feasible, keep it as an upper candidate (hi=mid); otherwise raise lo past it.

  4. 4
    Lines 17Return the threshold

    lo converges to the smallest feasible capacity.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • days == 1 (answer is sum of all weights)
  • days == len(weights) (answer is max single weight)
  • All weights equal
  • A single package (answer equals its weight)
!

Common beginner mistakes

  • Starting lo at 0 or 1 instead of max(weights), which lets an unshippable package slip through the feasibility check
  • Resetting the running load incorrectly - remember to add the current weight to the new day
  • Using lo <= hi with hi=mid, causing an infinite loop
  • Confusing 'minimize days' with 'minimize capacity' - here days is the fixed constraint
Check your understanding

Why must lo start at max(weights) rather than 0?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search