Capacity To Ship Packages Within D Days Solution

Problem

You have packages lined up at a port, each with a given weight, and a ship that must carry them all in order (you cannot reorder them) within a fixed number of days. Find the smallest ship capacity that gets every package shipped on time.

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: With capacity 15 you ship [1–5], [6–7], [8], [9], [10] across five days; no smaller capacity allows this in five days.

Intuition

The answer must be at least as large as the heaviest single package (otherwise that package can never be loaded) and at most the total weight (ship everything in one day). Between those two bounds, any capacity that works will continue to work if you increase it — so the feasibility function is monotone, which is exactly the condition that makes binary search valid. Instead of scanning every possible capacity, we can test the midpoint and halve the search space each time.

Approach 1 — Linear Scan (Brute Force)

Try every capacity from the minimum possible up to the maximum, returning the first one that allows shipping in time. This establishes the correct search space before we optimize.

Set min_capacity = max(weights), max_capacity = sum(weights).
For each candidate capacity from min_capacity to max_capacity:
Simulate loading packages in order; start a new day whenever adding the next package would exceed the capacity.
If the number of days used is ≤ days, return this capacity immediately.
Return max_capacity as a fallback (always valid).

1def shipWithinDays(weights: list[int], days: int) -> int:
2    def days_needed(capacity: int) -> int:
3        current_load = 0
4        shipping_days = 1
5        for weight in weights:
6            if current_load + weight > capacity:  # package doesn't fit; start a new day
7                shipping_days += 1
8                current_load = 0
9            current_load += weight
10        return shipping_days
11
12    for capacity in range(max(weights), sum(weights) + 1):
13        if days_needed(capacity) <= days:
14            return capacity
15    return sum(weights)

Time: O(n · S) where S = sum(weights) − max(weights), because we simulate O(n) for each candidate capacity.
Space: O(1) — no extra storage beyond a few counters.

Approach 2 — Binary Search on Capacity (Optimal)

Binary search over the valid capacity range. Each call to the feasibility check costs O(n), and we halve the range each step, giving O(n log S) total.

Set left = max(weights) (must be able to carry any single package) and right = sum(weights) (can ship all packages in one day).
While left < right, compute mid = left + (right - left) // 2.
Simulate shipping with capacity mid: iterate packages in order, accumulating load; when a package would exceed mid, start a new day.
If the simulation fits within days, the capacity works — search left half (right = mid).
Otherwise search right half (left = mid + 1).
Return left when the pointers meet — this is the minimum valid capacity.

1def shipWithinDays(weights: list[int], days: int) -> int:
2    def can_ship_in_time(capacity: int) -> bool:
3        shipping_days = 1
4        current_load = 0
5        for weight in weights:
6            if current_load + weight > capacity:  # package overflows today's load
7                shipping_days += 1
8                current_load = 0
9            current_load += weight
10        return shipping_days <= days
11
12    left, right = max(weights), sum(weights)
13    while left < right:
14        mid = left + (right - left) // 2
15        if can_ship_in_time(mid):
16            right = mid       # mid works; try to go smaller
17        else:
18            left = mid + 1    # mid is too small; must go larger
19    return left

Time: O(n log S) where S = sum(weights) — log S binary search iterations, each doing an O(n) scan.
Space: O(1) — only a handful of integer counters.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(n · S)	O(1)	Only for very small weight ranges; useful for understanding the problem
Binary Search	O(n log S)	O(1)	Always — the search space can be millions, making log S critical

Common Mistakes

Setting left = 0 instead of left = max(weights) — any capacity below the heaviest package is physically impossible; starting from 0 wastes up to max(weights) iterations and could cause an infinite loop if the check is accidentally true for 0.
Initializing shipping_days = 0 — you always need at least one day to ship any package, so start at 1, not 0.
Using right = sum(weights) - 1 as the upper bound — the sum itself is a valid capacity (ship everything in one day), so excluding it could cause binary search to miss the correct answer when only one day is available.
Using >= instead of > in the overflow check — if current_load + weight >= capacity incorrectly rejects an exact fit; a load that equals the capacity is fine and should continue on the same day.
Assuming packages can be reordered — the problem requires shipping in the given sequence; you cannot sort packages to minimize wasted space, which is why the greedy left-to-right fill is correct.

Capacity To Ship Packages Within D Days — Solution