Capacity To Ship Packages Within D Days: Binary Search on Answer

You are given an array of package weights and a number of days d. You must ship all packages in order within d days by choosing a ship capacity. Your task is to find the minimum capacity that lets you finish on time. This is LeetCode 1011: Capacity To Ship Packages Within D Days.

Example: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 returns 15.

Why this problem matters

Binary search on the answer is one of the most important binary search variations you will encounter. Instead of searching a sorted array for a specific value, you search over a range of candidate answers and use a feasibility check to narrow down to the optimal one. This pattern appears in a wide family of optimization problems: "find the minimum X such that some condition holds" or "find the maximum Y such that something is still valid."

Capacity To Ship Packages Within D Days is one of the cleanest examples of this pattern. The problem gives you a clear monotonic property: if a capacity of c is enough to ship everything in d days, then any capacity larger than c also works. If c is not enough, then anything smaller also fails. That monotonicity is exactly what binary search needs to cut the search space in half at each step.

Once you internalize this problem, you will recognize the same structure in Split Array Largest Sum (LeetCode 410), Koko Eating Bananas (LeetCode 875), and Minimum Number of Days to Make M Bouquets (LeetCode 1482). The skeleton is always the same: define the search range, write a greedy feasibility check, and binary search.

The key insight

You are not searching an array. You are searching the space of all possible ship capacities. The smallest valid capacity is at least max(weights), because the ship must be able to carry the heaviest single package. The largest meaningful capacity is sum(weights), because that would let you ship everything in a single day. Your answer lies somewhere in the range [max(weights), sum(weights)].

For any candidate capacity mid, you can check whether it is feasible by greedily simulating the shipping process. Walk through the weights array in order. Keep loading packages onto the current day until adding the next package would exceed the capacity. When that happens, start a new day. Count the total days needed. If the count is at most d, the capacity works.

Because feasibility is monotonic (once a capacity is large enough, all larger capacities also work), binary search finds the minimum feasible capacity efficiently.

Algorithm:

1. Set lo = max(weights), hi = sum(weights)
2. While lo < hi:
   • mid = (lo + hi) // 2
   • If can_ship(mid, days): hi = mid
   • Else: lo = mid + 1
3. Return lo

The solution

def ship_within_days(weights, days):
    def can_ship(capacity):
        day_count = 1
        current_load = 0
        for w in weights:
            if current_load + w > capacity:
                day_count += 1
                current_load = 0
            current_load += w
        return day_count <= days

    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_ship(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Let's walk through each piece of this solution.

The can_ship function is the greedy feasibility check. It simulates the shipping process for a given capacity. You start on day 1 with an empty ship. For each package, you check whether adding it to the current day's load would exceed the capacity. If it would, you start a new day and reset the load. Either way, you add the package to the current load. At the end, you check whether the total number of days used is at most d.

This greedy approach works because the packages must be shipped in order. You cannot rearrange them. So the optimal strategy for a given capacity is always to pack as many consecutive packages as possible into each day. There is no benefit to starting a new day early.

The binary search bounds are lo = max(weights) and hi = sum(weights). The lower bound is max(weights) because the ship must be able to carry at least the heaviest package. If the capacity were smaller than any single weight, that package could never be shipped. The upper bound is sum(weights) because a capacity equal to the total weight ships everything in one day.

The loop condition while lo < hi narrows the range until a single value remains. When lo == hi, that value is the answer.

hi = mid when feasible. If the current capacity works, it might be the answer, but a smaller capacity might also work. So you keep mid in the search range and look left.

lo = mid + 1 when infeasible. If the current capacity does not work, you need strictly more capacity. So you move lo past mid.

Visual walkthrough

The binary search narrows from a range of [10, 55] down to the exact answer of 15 in just a handful of steps. Each iteration cuts the search space roughly in half. Even if the sum of weights were a billion, binary search would converge in about 30 iterations.

Complexity analysis

Time is O(n log S) where n is the number of packages and S = sum(weights) - max(weights) is the size of the search range. The binary search runs O(log S) iterations. Each iteration calls can_ship, which scans the entire weights array in O(n) time. Multiplying these gives O(n log S). For the LeetCode constraints (n up to 50,000 and weights up to 500), S is at most 25,000,000, so log S is about 25. Total work is roughly 50,000 * 25 = 1,250,000 operations, which is very fast.

Space is O(1). The algorithm uses only a few integer variables (lo, hi, mid, day_count, current_load). No auxiliary data structures are needed.

The building blocks

1. Binary search on the answer

This is the core pattern. Instead of searching a sorted array for a target value, you search a range of candidate answers for the one that satisfies your condition.

lo, hi = min_possible, max_possible
while lo < hi:
    mid = (lo + hi) // 2
    if is_feasible(mid):
        hi = mid       # mid might be the answer, search left
    else:
        lo = mid + 1   # mid is too small, search right
return lo

The template is the same every time. What changes between problems is three things: (1) the bounds, (2) the feasibility function, and (3) whether you are minimizing or maximizing. For minimization problems like this one, you use hi = mid when feasible and lo = mid + 1 when not. For maximization, you flip the logic.

You will see this exact skeleton in Koko Eating Bananas, Split Array Largest Sum, and many other problems. Once you can write it from memory, the only challenge is designing the feasibility check.

2. Greedy feasibility check

The feasibility function for this problem is a greedy simulation. You walk through the packages in order, packing as many as possible into each day:

def can_ship(capacity):
    day_count = 1
    current_load = 0
    for w in weights:
        if current_load + w > capacity:
            day_count += 1
            current_load = 0
        current_load += w
    return day_count <= days

This greedy approach is optimal because the packages must stay in order. You cannot rearrange them to get a better packing. So the best you can do is load each day as full as possible before moving to the next. This "greedy packing" pattern shows up whenever you need to partition a sequence into contiguous groups subject to a constraint.

Edge cases

• d = 1: you must ship everything in one day, so the answer is sum(weights). The binary search handles this naturally because any capacity less than the sum requires more than one day.
• d = len(weights): one package per day, so the answer is max(weights). Again, binary search converges to this since lo starts at max(weights) and every feasibility check with that capacity passes.
• All equal weights: if every package weighs the same, the answer is ceil(n / d) * weight. The greedy check packs floor(capacity / weight) packages per day and the binary search finds the tightest capacity.
• Single package: the answer is that package's weight. Only one day is needed regardless of d.
• Very large d: if d is much larger than n, you still only need n days at most (one package per day), so the answer is max(weights).

From understanding to recall

The logic behind this problem is clean. Binary search the capacity range, greedily check whether each candidate works, and converge on the minimum. You likely understand it right now. But understanding and recalling under pressure are different skills.

Three weeks from now, will you remember whether the loop condition is lo < hi or lo <= hi? Will you set hi = mid or hi = mid - 1 when the capacity is feasible? Will lo start at 1, at max(weights), or at something else? These details are small but they determine whether your solution passes or fails. Spaced repetition drills them into long-term memory. You write the solution from scratch today, again tomorrow, then in three days, then in a week. After a few rounds, the binary search on answer template is automatic. You see "find the minimum capacity" and the code writes itself.

Related posts

• Koko Eating Bananas - Same binary search on answer pattern, searching for minimum eating speed
• Split Array Largest Sum - Minimize the maximum partition sum using binary search on the answer
• Find Minimum in Rotated Sorted Array - A different binary search variant where the search condition changes but the template stays the same

CodeBricks breaks Capacity To Ship Packages into its binary search on answer and greedy feasibility building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a binary search on answer problem shows up in your interview, you do not think about it. You just write it.