Capacity To Ship Packages Within D Days

Description

A conveyor belt has packages that must be shipped from one port to another within days days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages in the order given by weights (we cannot skip or rearrange packages). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Key observations:

Packages must be loaded in order — you cannot reorder them.
Each day, you load consecutive packages until adding the next one would exceed the ship's capacity. Then you stop loading for that day.
You need to find the minimum capacity such that all packages can be shipped in at most days days.

Examples

Example 1

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

Output: 15

Explanation: A ship capacity of 15 can ship all packages in 5 days:

Day 1: [1, 2, 3, 4, 5] → total weight = 15
Day 2: [6, 7] → total weight = 13
Day 3: [8] → total weight = 8
Day 4: [9] → total weight = 9
Day 5: [10] → total weight = 10

No capacity smaller than 15 can do it in 5 days.

Example 2

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

Output: 6

Explanation: A ship capacity of 6 ships all packages in 3 days:

Day 1: [3, 2] → total weight = 5 ≤ 6
Day 2: [2, 4] → total weight = 6 ≤ 6
Day 3: [1, 4] → total weight = 5 ≤ 6

Capacity 5 would need 4 days, which exceeds the 3-day limit.

Example 3

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

Output: 3

Explanation: A ship capacity of 3 ships all packages in 4 days:

Day 1: [1, 2] → total weight = 3 ≤ 3
Day 2: [3] → total weight = 3 ≤ 3
Day 3: [1, 1] → total weight = 2 ≤ 3

Only 3 days needed ≤ 4. Capacity 2 would fail because the package with weight 3 cannot fit on the ship at all.

Constraints

1 ≤ days ≤ weights.length ≤ 5 × 10^4
1 ≤ weights[i] ≤ 500

Editorial

Brute Force - Linear Search

Intuition

Let's think about what ship capacities even make sense to try.

The ship must be able to carry at least the heaviest single package — otherwise that package could never be loaded. So the minimum possible capacity is max(weights).

The maximum useful capacity is sum(weights) — a ship that big could carry everything in a single day, so there is no reason to go higher.

The answer must lie somewhere in the range [max(weights), sum(weights)].

The brute force idea is straightforward: try every capacity starting from the smallest (max(weights)) and going upward. For each candidate capacity, simulate the shipping process — greedily load packages day by day, and count how many days are needed. The first capacity that needs at most days days is our answer.

This is like trying on shoes from smallest to largest — the first pair that fits is the one you buy.

Step-by-Step Explanation

Let's trace through weights = [3, 2, 2, 4, 1, 4], days = 3.

The search range for capacity is [max(weights), sum(weights)] = [4, 16].

Try capacity = 4:

Day 1: Load 3 (total=3). Next is 2, 3+2=5 > 4 → stop. Day 1 ships [3].
Day 2: Load 2 (total=2). Next is 2, 2+2=4 ≤ 4 → load. Total=4. Next is 4, 4+4=8 > 4 → stop. Day 2 ships [2, 2].
Day 3: Load 4 (total=4). Next is 1, 4+1=5 > 4 → stop. Day 3 ships [4].
Day 4: Load 1 (total=1). Next is 4, 1+4=5 > 4 → stop. Day 4 ships [1].
Day 5: Load 4 (total=4). Day 5 ships [4].
Needed 5 days > 3. Capacity 4 fails.

Try capacity = 5:

Day 1: Load 3 (total=3). Next is 2, 3+2=5 ≤ 5 → load. Total=5. Next is 2, 5+2=7 > 5 → stop. Day 1 ships [3, 2].
Day 2: Load 2 (total=2). Next is 4, 2+4=6 > 5 → stop. Day 2 ships [2].
Day 3: Load 4 (total=4). Next is 1, 4+1=5 ≤ 5 → load. Total=5. Next is 4, 5+4=9 > 5 → stop. Day 3 ships [4, 1].
Day 4: Load 4 (total=4). Day 4 ships [4].
Needed 4 days > 3. Capacity 5 fails.

Try capacity = 6:

Day 1: Load 3 (total=3). Next is 2, 3+2=5 ≤ 6 → load. Total=5. Next is 2, 5+2=7 > 6 → stop. Day 1 ships [3, 2].
Day 2: Load 2 (total=2). Next is 4, 2+4=6 ≤ 6 → load. Total=6. Next is 1, 6+1=7 > 6 → stop. Day 2 ships [2, 4].
Day 3: Load 1 (total=1). Next is 4, 1+4=5 ≤ 6 → load. Total=5. No more packages. Day 3 ships [1, 4].
Needed 3 days = 3 ≤ days. Capacity 6 works!

Return 6.

Linear Search — Try Each Capacity Until One Works — Watch as we simulate shipping with increasing capacities. For each capacity, we greedily pack consecutive packages until the ship is full, then start a new day.

Algorithm

Compute the search range: low = max(weights), high = sum(weights).
For each candidate capacity from low to high:
a. Simulate shipping: iterate through weights in order, greedily loading packages onto each day until the next package would exceed the capacity.
b. Count the total number of days needed.
c. If days_needed ≤ days, return this capacity — it is the minimum since we started from the smallest possible.
(The loop is guaranteed to find an answer since capacity = sum(weights) always works in 1 day.)

Code

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int low = *max_element(weights.begin(), weights.end());
        int high = accumulate(weights.begin(), weights.end(), 0);

        for (int capacity = low; capacity <= high; capacity++) {
            int daysNeeded = 1;
            int currentLoad = 0;

            for (int w : weights) {
                if (currentLoad + w > capacity) {
                    daysNeeded++;
                    currentLoad = 0;
                }
                currentLoad += w;
            }

            if (daysNeeded <= days) {
                return capacity;
            }
        }

        return high;
    }
};

class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        low = max(weights)
        high = sum(weights)

        for capacity in range(low, high + 1):
            days_needed = 1
            current_load = 0

            for w in weights:
                if current_load + w > capacity:
                    days_needed += 1
                    current_load = 0
                current_load += w

            if days_needed <= days:
                return capacity

        return high

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int low = 0;
        int high = 0;

        for (int w : weights) {
            low = Math.max(low, w);
            high += w;
        }

        for (int capacity = low; capacity <= high; capacity++) {
            int daysNeeded = 1;
            int currentLoad = 0;

            for (int w : weights) {
                if (currentLoad + w > capacity) {
                    daysNeeded++;
                    currentLoad = 0;
                }
                currentLoad += w;
            }

            if (daysNeeded <= days) {
                return capacity;
            }
        }

        return high;
    }
}

Complexity Analysis

Time Complexity: O(n × S) where S = sum(weights) - max(weights)

We try up to S different capacity values. For each capacity, we scan all n packages to simulate the shipping process. In the worst case, with n = 50,000 and weights up to 500, S can be as large as 25,000,000 - 500 ≈ 25 million. Multiplied by n = 50,000 gives roughly 1.25 × 10^12 operations — far too slow.

Space Complexity: O(1)

We only use a few variables (capacity, daysNeeded, currentLoad) regardless of input size.

Why This Approach Is Not Efficient

The linear search checks every capacity from max(weights) to sum(weights). With constraints up to n = 50,000 and weights up to 500, the total sum can reach 25,000,000. That means we might try millions of capacities, and for each one we scan all n packages — resulting in roughly O(n × sum) = O(50,000 × 25,000,000) ≈ 10^12 operations. This is orders of magnitude beyond the typical 10^8 operation limit.

The key insight that makes improvement possible: the feasibility function is monotonic. If a capacity of C can ship all packages within days days, then any capacity C' > C can also do it (since a bigger ship can carry at least as much). Conversely, if capacity C fails, every smaller capacity also fails.

This monotonic property — where all "fail" values are below a threshold and all "pass" values are above it — is the textbook setup for binary search on the answer. Instead of trying capacities one by one, we can binary search to find the exact threshold, reducing the number of candidates we check from O(sum) to O(log(sum)).

Comparison chart showing O(n × sum) brute force vs O(n × log(sum)) binary search

Optimal Approach - Binary Search on Answer

Intuition

Instead of trying every capacity one by one, we can use binary search to find the minimum feasible capacity.

Here is why binary search works: imagine lining up all possible capacities from max(weights) to sum(weights). For each capacity, we can ask: "Can we ship all packages in at most days days?" The answers form a pattern like:

Capacity: 4  5  6  7  8  9  10 ... 16
Feasible: N  N  Y  Y  Y  Y  Y  ... Y

All the "No" answers are on the left, and all the "Yes" answers are on the right. There is a clean boundary — the first "Yes" is our answer. This is exactly the pattern binary search is designed to find.

The binary search works like this:

Set low = max(weights) and high = sum(weights).
Pick the middle capacity mid = (low + high) / 2.
Simulate shipping with capacity mid. If it works (needs ≤ days days), the answer might be mid or something smaller — search left by setting high = mid.
If it fails (needs more than days days), the answer must be larger — search right by setting low = mid + 1.
When low == high, we have found the minimum feasible capacity.

The simulation for each candidate capacity is the same greedy scan as the brute force — iterate through packages in order, accumulate weight, and start a new day whenever the next package would exceed the capacity. This takes O(n) per check. But now we only do O(log(sum)) checks instead of O(sum), making the total time O(n × log(sum)).

Step-by-Step Explanation

Let's trace through weights = [3, 2, 2, 4, 1, 4], days = 3.

Search range: low = max(3,2,2,4,1,4) = 4, high = 3+2+2+4+1+4 = 16.

Iteration 1: mid = (4 + 16) / 2 = 10
Simulate with capacity 10:

Day 1: 3+2+2 = 7. Next is 4: 7+4=11 > 10, so Day 1 = [3,2,2] (total=7). Start new day.
Day 2: 4+1+4 = 9 ≤ 10. Day 2 = [4,1,4] (total=9). All done.
days_needed = 2 ≤ 3 ✓. Capacity 10 works, but maybe smaller works too. Set high = 10.

Iteration 2: low=4, high=10, mid = (4 + 10) / 2 = 7
Simulate with capacity 7:

Day 1: 3+2+2 = 7 ≤ 7. Next is 4: 7+4=11 > 7. Day 1 = [3,2,2] (total=7).
Day 2: 4+1 = 5 ≤ 7. Next is 4: 5+4=9 > 7. Day 2 = [4,1] (total=5).
Day 3: 4 = 4 ≤ 7. Day 3 = [4] (total=4).
days_needed = 3 ≤ 3 ✓. Works! Set high = 7.

Iteration 3: low=4, high=7, mid = (4 + 7) / 2 = 5
Simulate with capacity 5:

Day 1: 3+2 = 5 ≤ 5. Next is 2: 5+2=7 > 5. Day 1 = [3,2] (total=5).
Day 2: 2 = 2. Next is 4: 2+4=6 > 5. Day 2 = [2] (total=2).
Day 3: 4+1 = 5 ≤ 5. Next is 4: 5+4=9 > 5. Day 3 = [4,1] (total=5).
Day 4: 4 = 4. Day 4 = [4] (total=4).
days_needed = 4 > 3 ✗. Too many days. Set low = 6.

Iteration 4: low=6, high=7, mid = (6 + 7) / 2 = 6
Simulate with capacity 6:

Day 1: 3+2 = 5 ≤ 6. Next is 2: 5+2=7 > 6. Day 1 = [3,2] (total=5).
Day 2: 2+4 = 6 ≤ 6. Next is 1: 6+1=7 > 6. Day 2 = [2,4] (total=6).
Day 3: 1+4 = 5 ≤ 6. No more packages. Day 3 = [1,4] (total=5).
days_needed = 3 ≤ 3 ✓. Works! Set high = 6.

Now low = 6, high = 6. Loop ends. Return 6.

We found the answer in just 4 iterations instead of trying all capacities from 4 to 6 and simulating for each.

Binary Search on Answer — Finding Minimum Ship Capacity — Watch how binary search narrows the capacity range by half each iteration, checking feasibility with a greedy simulation. The secondary row shows day assignments for each package.

Algorithm

Set low = max(weights) (minimum possible capacity — must carry the heaviest package).
Set high = sum(weights) (maximum useful capacity — carry everything in one day).
While low < high:
a. Compute mid = low + (high - low) / 2 (avoids integer overflow).
b. Simulate shipping with capacity mid:
- Initialize days_needed = 1, current_load = 0.
- For each weight w in weights:
  - If current_load + w > mid, start a new day: increment days_needed, reset current_load = 0.
  - Add w to current_load.
    c. If days_needed ≤ days, capacity mid is sufficient — set high = mid (look for something smaller or equal).
    d. Else, capacity mid is too small — set low = mid + 1 (need larger capacity).
Return low (which equals high at this point).

Code

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int low = *max_element(weights.begin(), weights.end());
        int high = accumulate(weights.begin(), weights.end(), 0);

        while (low < high) {
            int mid = low + (high - low) / 2;

            // Simulate shipping with capacity = mid
            int daysNeeded = 1;
            int currentLoad = 0;
            for (int w : weights) {
                if (currentLoad + w > mid) {
                    daysNeeded++;
                    currentLoad = 0;
                }
                currentLoad += w;
            }

            if (daysNeeded <= days) {
                high = mid;  // mid works, try smaller
            } else {
                low = mid + 1;  // mid too small, need bigger
            }
        }

        return low;
    }
};

class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        low = max(weights)
        high = sum(weights)

        while low < high:
            mid = low + (high - low) // 2

            # Simulate shipping with capacity = mid
            days_needed = 1
            current_load = 0
            for w in weights:
                if current_load + w > mid:
                    days_needed += 1
                    current_load = 0
                current_load += w

            if days_needed <= days:
                high = mid  # mid works, try smaller
            else:
                low = mid + 1  # mid too small, need bigger

        return low

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

        while (low < high) {
            int mid = low + (high - low) / 2;

            // Simulate shipping with capacity = mid
            int daysNeeded = 1;
            int currentLoad = 0;
            for (int w : weights) {
                if (currentLoad + w > mid) {
                    daysNeeded++;
                    currentLoad = 0;
                }
                currentLoad += w;
            }

            if (daysNeeded <= days) {
                high = mid;  // mid works, try smaller
            } else {
                low = mid + 1;  // mid too small, need bigger
            }
        }

        return low;
    }
}

Complexity Analysis

Time Complexity: O(n × log(S)) where S = sum(weights) - max(weights)

Binary search runs for at most log₂(S) iterations. In each iteration, we simulate shipping by scanning all n packages in O(n) time. With worst-case constraints (n = 50,000, max sum ≈ 25,000,000), we get roughly 50,000 × log₂(25,000,000) ≈ 50,000 × 25 = 1,250,000 operations — well within time limits.

Space Complexity: O(1)

We only use a fixed number of variables (low, high, mid, daysNeeded, currentLoad) regardless of input size. No additional data structures are needed.

Comparison:

Approach	Time	Space	Practical Ops (worst case)
Brute Force (Linear)	O(n × S)	O(1)	~1.25 × 10^12 (TLE)
Binary Search on Answer	O(n × log S)	O(1)	~1.25 × 10^6 (fast)

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Capacity To Ship Packages Within D Days

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force - Linear Search

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Binary Search on Answer

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis