Capacity To Ship Packages Within D Days

Master this topic with zero to advance depth.

Capacity To Ship Packages Within D Days

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]. Find the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Medium

Examples

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

Approach 1

Level I: Brute Force (Try Every Capacity)

Intuition

The minimum possible capacity is max(weights) (must ship heaviest package) and maximum is sum(weights) (all in one day). Try each value from min ascending and try to simulate — find the first one that ships all packages within D days.

⏱ O(N * (Sum-Max)) — for each candidate capacity we simulate the entire ship.💾 O(1) — constant variables.

Detailed Dry Run

Input: weights=[1,2,3,4,5,6,7,8,9,10], days=5 Min capacity = max = 10. Try 10: simulate → days used = 10 (too many). Try 15: simulate [1-5=15], [6-8=21 split], check... Actually enumerate until 15 fits in 5 days.

java

public class Solution {
    private int daysNeeded(int[] weights, int cap) {
        int days = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > cap) { days++; cur = 0; }
            cur += w;
        }
        return days;
    }
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) { lo = Math.max(lo, w); hi += w; }
        for (int cap = lo; cap <= hi; cap++) {
            if (daysNeeded(weights, cap) <= days) return cap;
        }
        return hi;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.shipWithinDays(new int[]{1,2,3,4,5,6,7,8,9,10}, 5)); // 15
    }
}

⚠️ Common Pitfalls & Tips

This tries every integer from max to sum. It's TLE for large inputs. Binary Search on Answer reduces this from O(Sum) iterations to O(log(Sum)) iterations.

Approach 2

Level II: Recursive Binary Search on Answer

Intuition

Wrap the binary search logic in a recursive function. The search space is still the same: [max(weights), sum(weights)].

⏱ $O(N \log(Sum))$💾 $O(\log(Sum))$ due to recursion stack.

Detailed Dry Run

lo=10, hi=55. mid=32. feasible? Yes. Recurse [10, 32].

java

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) { lo = Math.max(lo, w); hi += w; }
        return search(weights, days, lo, hi);
    }
    private int search(int[] weights, int days, int lo, int hi) {
        if (lo >= hi) return lo;
        int mid = lo + (hi - lo) / 2;
        if (canShip(weights, days, mid)) return search(weights, days, lo, mid);
        return search(weights, days, mid + 1, hi);
    }
    private boolean canShip(int[] weights, int days, int cap) {
        int need = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > cap) { need++; cur = 0; }
            cur += w;
        }
        return need <= days;
    }
}

Approach 3

Level III: Optimal (Binary Search on Answer)

Intuition

The answer (minimum capacity) lies in the range [max(weights), sum(weights)]. This range is MONOTONE: if capacity C works, C+1 also works. If capacity C doesn't work, C-1 doesn't either. This is the 'feasibility check + binary search' pattern — search for the LEFT boundary of feasible capacities.

⏱ O(N log(Sum)) — binary search * feasibility simulation.💾 O(1) — constant variables.

Detailed Dry Run

weights=[1,2,3,4,5,6,7,8,9,10], days=5. Range: lo=10, hi=55

Step	lo	hi	mid	simulate(mid)	days needed	<=5?	Action
1	10	55	32	[1..6]=21,[7,8]=15,[9]=9,[10]=10	4	Yes	hi=32
2	10	32	21	[1..6]=21,[7,8]=15,[9,10]=19	3	Yes	hi=21
3	10	21	15	[1-5]=15,[6-8]=21 wait 21>15, split...	5	Yes	hi=15
4	10	15	12	[1-5]=15? 15>12, split...	6	No	lo=13
5	13	15	14	simulate → 5 days	Yes	hi=14
6	13	14	13	simulate → 6	No	lo=14
lo==hi==15... → return 15

java

public class Solution {
    private boolean canShip(int[] weights, int days, int cap) {
        int need = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > cap) { need++; cur = 0; }
            cur += w;
        }
        return need <= days;
    }
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) { lo = Math.max(lo, w); hi += w; }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, days, mid)) hi = mid; // feasible, try smaller
            else lo = mid + 1;                          // not feasible, need larger
        }
        return lo;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.shipWithinDays(new int[]{1,2,3,4,5,6,7,8,9,10}, 5)); // 15
        System.out.println(sol.shipWithinDays(new int[]{3,2,2,4,1,4}, 3));           // 6
    }
}

⚠️ Common Pitfalls & Tips

The search range is [max(weights), sum(weights)]. Use lo < hi (not <=). When feasible, set hi = mid (not mid-1) to keep candidate in range. The feasibility function simulates greedy packing: always add to current day until capacity exceeded, then start new day.

← Previous QuestionFind K Closest Elements

Next Question →Split Array Largest Sum

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.