Pseudo-code

text
min_cap = max(weights)
max_cap = sum(weights)

for capacity from min_cap to max_cap:
    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

Time Complexity Analysis

The time complexity is $O(N \cdot S)$, where $N$ is the number of packages and $S$ is the sum of all weights (representing the search space size). Since the sum of weights can be significantly larger than $N$ (up to $500 \times 5 \cdot 10^4 = 2.5 \cdot 10^7$), this approach will result in a Time Limit Exceeded (TLE) error. The search space is too large to traverse linearly.

Core Insight for Capacity To Ship Packages Within D Days

The key intuition is recognizing that the property "can ship within D days" is monotonic with respect to capacity.

1. Monotonicity: If a ship capacity of C is sufficient to ship all packages within D days, then any capacity C + 1 is also sufficient (it will take D days or fewer). Conversely, if capacity C is insufficient, then any capacity C - 1 is also insufficient.
2. Search Space Definition:
   • Lower Bound (left): The capacity cannot be smaller than the heaviest single package, max(weights). If it were, that package could never be loaded.
   • Upper Bound (right): The capacity never needs to exceed the total weight of all packages, sum(weights). This capacity guarantees shipping in exactly 1 day.
3. Condition Function: We can define a function feasible(capacity) that returns true if the packages can be shipped within days using that capacity, and false otherwise. This function runs in linear time $O(N)$.

Visual Description: Imagine the search space as a sorted array of candidate capacities ranging from max(weights) to sum(weights). If we apply the feasible function to each value, the results would look like a sequence of False values followed by a sequence of True values (e.g., [F, F, F, T, T, T]). Our goal is to find the index of the first True in this virtual array.

Execution Flow

Consider weights = [1, 2, 3, 4, 5], days = 3.

1. Initialization:

   • left = 5 (max weight)
   • right = 15 (sum of weights)

2. Iteration 1:

   • mid = (5 + 15) // 2 = 10.
   • Check feasible(10):
     • Day 1: 1+2+3+4 = 10 (Full).
     • Day 2: 5.
     • Total days: 2. Since 2 <= 3, returns True.
   • Logic: 10 works, try smaller. right = 10.

3. Iteration 2:

   • left = 5, right = 10.
   • mid = (5 + 10) // 2 = 7.
   • Check feasible(7):
     • Day 1: 1+2+3 = 6. (Adding 4 would exceed 7).
     • Day 2: 4. (Adding 5 would exceed 7).
     • Day 3: 5.
     • Total days: 3. Since 3 <= 3, returns True.
   • Logic: 7 works, try smaller. right = 7.

4. Iteration 3:

   • left = 5, right = 7.
   • mid = (5 + 7) // 2 = 6.
   • Check feasible(6):
     • Day 1: 1+2+3 = 6.
     • Day 2: 4.
     • Day 3: 5.
     • Total days: 3. Since 3 <= 3, returns True.
   • Logic: 6 works, try smaller. right = 6.

5. Iteration 4:

   • left = 5, right = 6.
   • mid = (5 + 6) // 2 = 5.
   • Check feasible(5):
     • Day 1: 1+2 = 3. (Adding 3 exceeds 5).
     • Day 2: 3. (Adding 4 exceeds 5).
     • Day 3: 4. (Adding 5 exceeds 5).
     • Day 4: 5.
     • Total days: 4. Since 4 > 3, returns False.
   • Logic: 5 is too small. left = 6.

6. Termination:

   • left is 6, right is 6. Loop ends.
   • Return left (6).

Proof of Correctness

The algorithm relies on the monotonicity of the problem. Let $f(c)$ be a boolean function indicating if capacity $c$ is valid.

1. Invariant: The optimal solution always lies within the interval [left, right].
2. Initialization: We know the answer must be at least max(weights) and at most sum(weights).
3. Maintenance:
   • If mid is valid ($f(mid)$ is true), then mid could be the answer, or the answer is smaller. We reduce the range to [left, mid]. The answer is still in range.
   • If mid is invalid ($f(mid)$ is false), then mid and anything smaller is also invalid. We reduce the range to [mid + 1, right]. The answer is still in range.
4. Termination: The range shrinks by half at each step. When left == right, the search space has converged to the single smallest valid capacity.

Reference Implementation

C++ Solution for LeetCode 1011

cpp
#include <vector>
#include <numeric>
#include <algorithm>

class Solution {
public:
    int shipWithinDays(std::vector<int>& weights, int days) {
        // Initialize binary search bounds
        int left = 0;
        int right = 0;
        
        for (int w : weights) {
            left = std::max(left, w);
            right += w;
        }

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

private:
    bool canShip(const std::vector<int>& weights, int days, int capacity) {
        int daysNeeded = 1;
        int currentLoad = 0;
        
        for (int w : weights) {
            if (currentLoad + w > capacity) {
                daysNeeded++;
                currentLoad = 0;
            }
            currentLoad += w;
        }
        
        return daysNeeded <= days;
    }
};

Java Solution for LeetCode 1011

java
class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0;
        int right = 0;
        
        // Determine bounds
        for (int w : weights) {
            left = Math.max(left, w);
            right += w;
        }
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (canShip(weights, days, mid)) {
                right = mid; // Feasible, try to minimize
            } else {
                left = mid + 1; // Not feasible, increase capacity
            }
        }
        
        return left;
    }
    
    private boolean canShip(int[] weights, int days, int capacity) {
        int daysNeeded = 1;
        int currentLoad = 0;
        
        for (int w : weights) {
            if (currentLoad + w > capacity) {
                daysNeeded++;
                currentLoad = 0;
            }
            currentLoad += w;
        }
        
        return daysNeeded <= days;
    }
}

Python Solution for LeetCode 1011

python
class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def can_ship(capacity):
            days_needed = 1
            current_load = 0
            for w in weights:
                if current_load + w > capacity:
                    days_needed += 1
                    current_load = 0
                current_load += w
            return days_needed <= days

        # Initialize bounds
        left = max(weights)
        right = sum(weights)

        while left < right:
            mid = left + (right - left) // 2
            if can_ship(mid):
                right = mid  # Valid capacity, try smaller
            else:
                left = mid + 1  # Invalid, need larger capacity
        
        return left