Skip to main content
DSA patterns

Capacity To Ship Packages Within D Days

mediumBinary search

Problem statement

Packages must be shipped in the order given by the list weights. Each day, one ship loads packages from the front of the remaining line, one after another, as long as the total weight loaded that day does not go above the ship's capacity. Packages cannot be reordered or split, and the next day continues where the previous day stopped.

Given weights and a number of days, return the smallest ship capacity that gets every package shipped within days days.

Examples

Example 1

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

Output: 15

Explanation: With capacity 15 the days are [1, 2, 3, 4, 5], [6, 7], [8], [9], [10]. A capacity of 14 would need six days: [1, 2, 3, 4], [5, 6], [7], [8], [9], [10].

Example 2

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

Output: 6

Explanation: With capacity 6 the days are [3, 2], [2, 4], [1, 4]. With capacity 5 the packages need four days: [3, 2], [2], [4, 1], [4].

Hints

Hint 1: The capacity can never be less than the heaviest package, and a capacity equal to the total weight always finishes in one day. The answer lies between these two numbers.

Approach

Optimal: Binary search on the capacity

Intuition

The brute force tests capacities one by one, but the answer has a pattern: if capacity c finishes in time, every bigger capacity does too. So the capacities form a row of "no, no, no, yes, yes, yes", and we want the first "yes". That is exactly what binary search finds. Look at the middle capacity: if it works, the answer is it or something smaller; if it does not, the answer is bigger. This is faster because each check throws away half of all remaining capacities.

Steps

  1. Set lo = max(weights) (every package must fit) and hi = sum(weights) (everything in one day).
  2. While lo < hi, compute mid = lo + (hi - lo) // 2.
  3. If days_needed(mid) <= days, mid works, so set hi = mid.
  4. Otherwise mid is too small, so set lo = mid + 1.
  5. When lo == hi, return lo.

Dry run

weights = [3, 2, 2, 4, 1, 4], days = 3, so lo = 4 and hi = 16

lo hi mid days needed action
4 16 10 2 works → hi = 10
4 10 7 3 works → hi = 7
4 7 5 4 too small → lo = 6
6 7 6 3 works → hi = 6
6 6 - - return 6

Edge cases: one package gives lo == hi, so the loop does not run and the answer is that package. If days is at least the number of packages, the answer is the heaviest package.

Complexity

Time O(n log S) - The capacity lies between the heaviest package and the total weight S, and each step of the binary search halves that range, so there are about log S steps. Every step runs the O(n) day-counting pass once. For 50,000 packages and a total weight of one billion that is about 30 passes instead of up to a billion.

Space O(1) - We keep `lo`, `hi`, `mid` and the counters of the helper. Nothing grows with the input. The list is only read.

class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def days_needed(cap: int) -> int:
            used, load = 1, 0
            for w in weights:
                if load + w > cap:
                    used += 1
                    load = 0
                load += w
            return used

        lo, hi = max(weights), sum(weights)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if days_needed(mid) <= days:
                hi = mid
            else:
                lo = mid + 1
        return lo


if __name__ == "__main__":
    print(Solution().shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))
    print(Solution().shipWithinDays([3, 2, 2, 4, 1, 4], 3))
RecapThe whole problem in a few lines, for the night before
  • Spot it: find the smallest value that makes something feasible, where bigger is always at least as good
  • Idea: binary search on the ship capacity between the heaviest package and the total weight; check feasibility by simulating the days greedily
  • Cost: O(n log(sum)) time, O(1) space
  • Trap: the low bound is the heaviest single package, not 1, and packages must ship in the given order

Interview follow-ups

  • Return the actual split of packages into days, not just the capacity.

    Once binary search gives the smallest capacity, run the greedy loader one more time with that capacity. Keep a list for the current day, and when the next package would push the day's total over the capacity, close the list and start a new one. The result is a list of lists in the original order. This costs one extra O(n) pass and O(n) space for the output. The split is not unique, but every split built this way respects the capacity and uses at most days days.

  • Packages may now be loaded in any order. How does the problem change?

    Each day becomes a bin of size capacity, so checking whether a capacity works is now a bin packing question, which is NP-hard in general. The greedy check from the fixed-order version is no longer correct, because the order of packages now changes the outcome. You can still binary search the capacity, with lower bound max(max(weights), ceil(sum / days)). The feasibility check then needs a heuristic such as first-fit decreasing, or backtracking for small inputs. A heuristic can overestimate the capacity, so the answer is only exact when the check is exact.

Frequently asked questions

It models batching work in a fixed order under a per-batch limit: splitting an ordered list of database migrations or log uploads into runs that each stay under a size or time cap, and finding the smallest cap that fits in a given number of maintenance windows. The same "binary search the answer" idea also sizes things like the smallest batch size or rate limit that meets a deadline.

Both binary search the answer with a check that only flips once. Here, packages are grouped in order into days, so the check is a greedy grouping pass. In Koko each pile is handled on its own with a ceiling division. If you can write one, the other is the same loop with a different check.

A capacity below the heaviest package can never ship it, but the greedy days_needed above does not notice that: it would open a new day and still overfill it. Starting at the maximum keeps every tested capacity valid.

If mid fits in days, the true answer is mid or smaller, so we keep mid inside the range with hi = mid. If it does not fit, mid itself is ruled out, so lo = mid + 1. Using hi = mid - 1 in the first case would throw away a valid answer.