LeetCode 1011 - Capacity To Ship Packages Within D Days

Link : https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

/**
 * LeetCode 1011 - Capacity To Ship Packages Within D Days
 * 
 * Problem: Given weights array and days D, find minimum ship capacity needed to ship all packages in D days.
 * Constraints:
 * - Packages must be shipped in order
 * - Can only ship packages using one ship per day
 * 
 * Approach: Binary Search on Answer Space
 * 1. Minimum capacity = max(weights) (ship must carry heaviest package)
 * 2. Maximum capacity = sum(weights) (ship can carry all packages in one day)
 * 3. For each capacity, check if we can ship all packages in D days
 * 
 * Time Complexity: O(n * log(sum(weights))) where n is length of weights array
 * Space Complexity: O(1) using constant extra space
 */
class ShipPackages {
    public int shipWithinDays(int[] weights, int days) {
        // Find search space boundaries
        int left = 0;    // minimum capacity
        int right = 0;   // maximum capacity

        for (int weight : weights) {
            left = Math.max(left, weight);  // heaviest package
            right += weight;                // sum of all weights
        }

        // Binary search for minimum valid capacity
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (canShipWithinDays(weights, days, mid)) {
                right = mid;    // Try smaller capacity
            } else {
                left = mid + 1; // Need larger capacity
            }
        }

        return left;
    }

    // Helper function to check if we can ship all packages in 'days' days with given capacity
    private boolean canShipWithinDays(int[] weights, int days, int capacity) {
        int daysNeeded = 1;
        int currentLoad = 0;

        for (int weight : weights) {
            if (currentLoad + weight > capacity) {
                daysNeeded++;
                currentLoad = weight;

                if (daysNeeded > days) {
                    return false;  // Early termination
                }
            } else {
                currentLoad += weight;
            }
        }

        return true;
    }

    /**
     * Key Insights:
     * 1. Binary Search Range:
     *    - Minimum: max(weights) - must handle heaviest package
     *    - Maximum: sum(weights) - worst case, ship all in one day
     * 
     * 2. Optimizations:
     *    - Early termination in canShipWithinDays
     *    - Packages must be shipped in order (greedy approach works)
     * 
     * 3. Similar Problems:
     *    - LC 875: Koko Eating Bananas
     *    - LC 1891: Cutting Ribbons
     *    - LC 410: Split Array Largest Sum
     * 
     * 4. Interview Tips:
     *    - Discuss why binary search works (monotonic property)
     *    - Consider edge cases: days = 1, days = weights.length
     *    - Mention possible follow-ups: what if order doesn't matter?
     */
}