Capacity to Ship Packages Within D Days

1. The Core Problem Statement & Real-World Framing

When given an array of package weights and a specific number of days ($D$), the goal is to determine the least capacity a ship must have to successfully transport all packages sequentially within $D$ days.

Real-Life Analogy: The Daily Cargo Ferry

Imagine you run a logistics service across a river. You have a single cargo ship that makes exactly one trip per day. You have $N$ customer packages lined up on the dock, each with a fixed weight (e.g., $1\text{ kg}, 2\text{ kg}, \dots, 10\text{ kg}$).

• If your ship has a tiny capacity (e.g., $10\text{ kg}$), it fills up quickly. Heavy packages get left behind on the dock, forcing you to stretch the shipping process across many days (e.g., 7 days instead of your target 5 days).
• If your ship has a massive capacity (e.g., $100\text{ kg}$), you can load every single package on day one and finish instantly. However, building or renting a massive ship is unnecessarily expensive.
• The challenge is to find the absolute minimum ship capacity that allows you to clear the dock within your deadline of $D$ days.

2. Analyzing the Search Space: Establishing Lower & Upper Bounds

Before searching for the optimal capacity, we must determine the theoretical boundaries (minimum and maximum possible values) for the ship's capacity.

• Lower Bound ($\text{Low}$): Can a ship have a capacity smaller than the heaviest single package?
  • No. If there is a package weighing $10\text{ kg}$, a ship with a capacity of $8\text{ kg}$ could never load that package, making it impossible to ship all items. Therefore, $\text{Low} = \max(\text{weights})$.
• Upper Bound ($\text{High}$): What is the maximum capacity we would ever need?
  • If the ship's capacity equals the sum of all package weights, we can load every single item on the very first day. Any capacity larger than the sum is redundant. Therefore, $\text{High} = \sum(\text{weights})$.

Thus, the answer is guaranteed to lie within the inclusive range:

3. Naive Approach: Linear Search from Max to Sum

The most intuitive approach is to test every possible ship capacity sequentially, starting from $\max(\text{weights})$ up to $\sum(\text{weights})$, until we find the first capacity that satisfies the $D$-day constraint.

Limitations of Linear Search

• Time Complexity: If the sum of weights is large, iterating linearly through every integer capacity takes $O(\text{sum} - \max) \times O(N)$ time, which results in a quadratic-like time complexity that will fail on large test cases in an interview.

4. Designing the Feasibility Function (findDays)

To evaluate whether a given ship capacity is workable, we need a helper function that calculates how many days it takes to ship all packages under a fixed capacity constraint.

Algorithm Logic

1. Start on day = 1 with a current load = 0.
2. Iterate through each package weight from left to right.
3. Check if adding the current package exceeds the ship's capacity:
   • If it exceeds: Increment the day counter (day++), and reset the load to the current package's weight.
   • If it fits: Add the package weight to the current day's load.
4. Return the total number of days required.

C++ Implementation of Feasibility Check

int findDays(vector<int>& weights, int capacity) {
    int days = 1;
    int load = 0;
    for (int i = 0; i < weights.size(); i++) {
        if (load + weights[i] > capacity) {
            days = days + 1; // Move to the next day
            load = weights[i]; // Load current package on the new day
        } else {
            load += weights[i]; // Keep loading on the current day
        }
    }
    return days;
}

5. Dry Run of Feasibility Function

Consider an array of weights: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (Sum = 55, Max = 10). Let's test a capacity of 10 with target $D = 5$.

• Final Result: A capacity of $10$ requires 7 days. Since $7 > 5$, capacity $10$ is invalid.

6. Optimized Approach: Binary Search on Answers

Since the search space $[\max, \text{sum}]$ is monotonically sorted (i.e., if capacity $C$ works, any capacity $> C$ also works; if $C$ fails, any capacity $< C$ also fails), we can apply Binary Search.

Binary Search Workflow

1. Set $\text{low} = \max(\text{weights})$ and $\text{high} = \sum(\text{weights})$.
2. Calculate $\text{mid} = \text{low} + (\text{high} - \text{low}) / 2$.
3. Pass mid as the test capacity into findDays(weights, mid).
4. Evaluate Feasibility:
   • If $\text{days required} \le D$, the capacity is possible. Record it (or rely on binary search convergence) and try to find a smaller capacity by moving $\text{high} = \text{mid} - 1$.
   • If $\text{days required} > D$, the capacity is too small. Increase capacity by moving $\text{low} = \text{mid} + 1$.
5. Repeat until $\text{low} > \text{high}$.

7. Step-by-Step Binary Search Execution Flow

8. Complete C++ Implementation

class Solution {
public:
    int findDays(vector<int>& weights, int capacity) {
        int days = 1;
        int load = 0;
        for (int i = 0; i < weights.size(); i++) {
            if (load + weights[i] > capacity) {
                days++;
                load = weights[i];
            } else {
                load += weights[i];
            }
        }
        return days;
    }

    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;
            int numberOfDays = findDays(weights, mid);
            
            if (numberOfDays <= days) {
                // Feasible capacity, try to find a smaller valid capacity on the left
                high = mid - 1;
            } else {
                // Too small capacity, increase capacity by searching the right half
                low = mid + 1;
            }
        }
        return low; // Low pointer points to the minimum valid capacity
    }
};

9. Complexity Analysis

10. Summary and Key Takeaways

• Problem Classification: This is a classic "Binary Search on Answers" problem where the answer range is bounded between the maximum element and the sum of elements.
• Lower Bound Rule: The minimum possible ship capacity can never be less than the single heaviest package in the dataset.
• Upper Bound Rule: The maximum sensible capacity is the sum of all package weights, allowing all items to be shipped in a single day.
• Monotonic Property: If a capacity $X$ can ship all packages within $D$ days, any capacity greater than $X$ will also work. If $Y$ fails, anything smaller than $Y$ will also fail.
• Helper Function Decoupling: Separating the day-counting logic into a helper function (findDays) keeps the binary search clean and modular.
• Pointer Convergence: When low <= high terminates, the low pointer naturally lands on the optimal minimum capacity.
• Performance Gain: Optimizing from a linear search to binary search reduces the time complexity from quadratic-like behavior to efficient logarithmic time ($O(\log(\text{range}) \cdot N)$).