1011. Capacity To Ship Packages Within D Days

Intuition

We need to find the minimum ship capacity such that all packages are shipped within a given number of days. Since packages must be loaded in order and cannot exceed the ship's capacity each day, increasing the ship's capacity can reduce the number of days needed.

This forms a monotonic search space, where increasing the capacity monotonically decreases the required number of days. Hence, we can apply binary search on the capacity range.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N*\log{N})$

Code

// Helper function to calculate the number of days required to ship all packages with given ship capacity
public int daysToShip(int[] packageWeights, int shipCapacity) {
    int currentLoad = 0, requiredDays = 0;

    for (int weight : packageWeights) {
        // If adding current weight exceeds the capacity, ship the load and start a new day
        if (currentLoad + weight > shipCapacity) {
            currentLoad = 0;
            requiredDays++;
        }
        currentLoad += weight;
    }

    // Account for the last day's shipment
    if (currentLoad > 0) requiredDays++;

    return requiredDays;
}

public int shipWithinDays(int[] packageWeights, int maxAllowedDays) {
    int minCapacity = 0, maxCapacity = 0, optimalCapacity = 0;

    // Initialize search bounds
    for (int weight : packageWeights) {
        minCapacity = Math.max(minCapacity, weight); // at least the heaviest package
        maxCapacity += weight; // at most all weights in one day
    }

    // Binary search for the minimum sufficient capacity
    while (minCapacity <= maxCapacity) {
        int midCapacity = (minCapacity + maxCapacity) / 2;

        int daysNeeded = daysToShip(packageWeights, midCapacity);

        if (daysNeeded <= maxAllowedDays) {
            // Capacity is sufficient, try to find a smaller one
            optimalCapacity = midCapacity;
            maxCapacity = midCapacity - 1;
        } else {
            // Not enough capacity, try a larger one
            minCapacity = midCapacity + 1;
        }
    }

    return optimalCapacity;
}