Minimum Shipping Capacity
Task example: Minimum Shipping Capacity
Find the smallest positive integer ship capacity that sends all packages within days days. Load packages in the given order without splitting them. The total weight loaded each day cannot exceed capacity. The input guarantees 1 <= days <= len(weights). Keep weights unchanged.
Capacity 6 groups the packages as [3, 2] | [2, 4] | [1, 4]: three days. Capacity 5 needs four days: [3, 2] | [2] | [4, 1] | [4]. Therefore the minimum is 6. Package order must stay unchanged.
Try every capacity: video explanation
weights = [3, 2, 2, 4, 1, 4], days = 3 → 6
Prefer reading? Follow the steps below.
- Try capacity from max(weights) through sum(weights). The ship must carry the heaviest package; the total weight always fits in one day. For each candidate, start needed = 1 and load = 0.
- Visit weights in order. If load + weight > capacity, start a new day: add 1 to needed and reset load to 0. Then add weight to load. Equality fits, so do not use >=.
- After all packages, return the first capacity with needed <= days. In the example, capacities 4, 5, and 6 require 5, 4, and 3 days. The first working capacity is 6.
Time complexity · O(n · R)
Let n = len(weights), S = sum(weights), and M = max(weights). There are R = S - M + 1 candidate capacities. Each check scans n packages: O(n · R) worst-case time.
Space complexity · O(1)
Only capacity, bounds, and counters are stored. The input is not copied: O(1) extra space.
Binary search: video explanation
weights = [3, 2, 2, 4, 1, 4], days = 3 → 6
Prefer reading? Follow the steps below.
- Set left = max(weights) and right = sum(weights). Search capacities, not array indices. For any fixed capacity, loading as many consecutive packages as fit into each day minimizes the days needed.
- While left < right, try capacity = (left + right) // 2. Count needed days with the same in-order loading check. Start a new day only when load + weight > capacity.
- If needed <= days, set right = capacity: this capacity works, and a smaller one might too. Otherwise set left = capacity + 1: this and every smaller capacity fail.
- When left == right, return left. The example tests capacities 10, 7, 5, and 6. Keep a successful capacity in the range; right = capacity - 1 could discard the answer.
Once a capacity works, every larger capacity works too. Binary search skips ranges instead of testing every capacity. Do not sort weights: the original package order is part of the task. Finishing in fewer than days days is allowed.
Time complexity · O(n · log(R + 1))
With R = sum(weights) - max(weights) + 1 candidates, each O(n) check halves the range. Including the initial scans and R = 1, time complexity is O(n · log(R + 1)).
Space complexity · O(1)
Only capacity, bounds, and counters are stored. The input is not copied: O(1) extra space.