Back to main article
LC 1011 Search on Answer Medium

Capacity to Ship Packages Within D Days

Structurally identical to Koko Bananas — just different domain language. Master Koko first and this one takes 5 minutes.

Problem

What are we solving?

Problem Statement

A conveyor belt has packages with weights given by array weights. We have days days to ship all packages. Packages must be shipped in order. The ship's daily capacity determines how many packages can be shipped each day. Return the minimum weight capacity of the ship that will result in all packages being shipped within days days.

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

Same pattern as Koko — different story

The structure is identical. We binary search the capacity (1 to sum of all weights). For each candidate capacity, we greedily simulate shipping: keep adding packages to the current day until adding the next would exceed capacity, then start a new day. Count total days needed and check if ≤ given days.

weights=[1..10], days=5 · Search space: capacity max(weights)..sum(weights)
condition: canShip(capacity, days)
c=10F
c=11F
c=14F
c=15T*
c=20T
c=55T
At capacity=15: days needed = 5. Minimum capacity that fits.
→

Search bounds: Lower bound = max(weights) — the ship must be able to carry the heaviest single package. Upper bound = sum(weights) — at this capacity, all packages ship in 1 day.

Solution

Clean implementation

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 0;
        for (int w : weights) { left = Math.max(left, w); right += w; }
        int boundary = right;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canShip(weights, mid, days)) {
                boundary = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return boundary;
    }

    private boolean canShip(int[] weights, int cap, int days) {
        int daysNeeded = 1, load = 0;
        for (int w : weights) {
            if (load + w > cap) { daysNeeded++; load = 0; }
            load += w;
        }
        return daysNeeded <= days;
    }
}
class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        left, right = max(weights), sum(weights)
        boundary = right

        while left <= right:
            mid = left + (right - left) // 2
            if self.can_ship(weights, mid, days):
                boundary = mid
                right = mid - 1
            else:
                left = mid + 1
        return boundary

    def can_ship(self, weights, cap, days):
        days_needed, load = 1, 0
        for w in weights:
            if load + w > cap:
                days_needed += 1
                load = 0
            load += w
        return days_needed <= days

Complexity

Time
O(n log S)
S = sum of weights. log S binary search steps, each O(n) simulation.
Space
O(1)
Constant extra space — simulation uses only accumulators.
↑ Pattern map