LeetCode 1011: Capacity To Ship Packages Within D Days

Problem Restatement

We have packages with weights given in an array weights.

A ship loads packages in order every day. Once a day’s load would exceed the ship’s capacity, we stop loading and start a new day.

We are given days, the maximum number of days allowed.

We need to return the minimum weight capacity of the ship so that all packages can be shipped within days days.

The official constraints state that 1 <= days <= weights.length <= 5 * 10^4 and 1 <= weights[i] <= 500.

Input and Output

Function shape:

def shipWithinDays(weights: list[int], days: int) -> int:
    ...

Examples

Example 1:

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

With capacity 15: day 1 gets [1,2,3,4,5], day 2 gets [6,7], day 3 gets [8], day 4 gets [9], day 5 gets [10]. Total 5 days. ✓

Answer:

15

Example 2:

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

With capacity 6: day 1 [3,2], day 2 [2,4], day 3 [1,4]. All fit in 3 days.

Answer:

6

Key Insight

The minimum possible capacity is max(weights) (must fit the heaviest package).

The maximum useful capacity is sum(weights) (ship everything in one day).

The answer is monotone: if capacity c works, any c' > c also works.

This makes binary search on the capacity applicable.

Algorithm

1. Set left = max(weights) and right = sum(weights).
2. While left < right:
   • mid = (left + right) // 2.
   • Check if capacity mid allows shipping within days days.
   • If yes, try smaller: right = mid.
   • If no, try larger: left = mid + 1.
3. Return left.

The feasibility check: greedily load packages day by day, counting how many days are needed.

Correctness

Binary search finds the smallest mid for which the feasibility check passes.

The feasibility check is greedy: load as many packages as possible each day without exceeding capacity. This uses the fewest days possible for a given capacity.

If the greedy check says days days suffice, the capacity works. If not, we need more capacity.

Edge Cases

• Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
• Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
• When the target is absent, the loop should still terminate and return the problem-specific failure value.

Complexity

Let n = len(weights) and S = sum(weights).

Common Pitfalls

• Do not mix inclusive and half-open bounds inside the same loop.
• Make sure each branch strictly reduces the search interval.

Implementation

class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def can_ship(capacity: int) -> bool:
            current = 0
            needed_days = 1
            for w in weights:
                if current + w > capacity:
                    needed_days += 1
                    current = 0
                current += w
            return needed_days <= days

        left = max(weights)
        right = sum(weights)

        while left < right:
            mid = (left + right) // 2
            if can_ship(mid):
                right = mid
            else:
                left = mid + 1

        return left

Code Explanation

The feasibility function can_ship simulates the loading process:

for w in weights:
    if current + w > capacity:
        needed_days += 1
        current = 0
    current += w

Start a new day when the current load would exceed capacity.

Binary search narrows the capacity range:

while left < right:
    mid = (left + right) // 2
    if can_ship(mid):
        right = mid
    else:
        left = mid + 1

When left == right, we have the minimum capacity.

Testing

def run_tests():
    s = Solution()

    assert s.shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5) == 15
    assert s.shipWithinDays([3, 2, 2, 4, 1, 4], 3) == 6
    assert s.shipWithinDays([1, 2, 3, 1, 1], 4) == 3
    assert s.shipWithinDays([1], 1) == 1

    print("all tests passed")

run_tests()