Course4all

Capacity To Ship Packages Within D Days

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Binary Search.

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
Steplohimidsimulate(mid)days needed<=5?Action
1105532[1..6]=21,[7,8]=15,[9]=9,[10]=104Yeshi=32
2103221[1..6]=21,[7,8]=15,[9,10]=193Yeshi=21
3102115[1-5]=15,[6-8]=21 wait 21>15, split...5Yeshi=15
4101512[1-5]=15? 15>12, split...6Nolo=13
5131514simulate → 5 daysYeshi=14
6131413simulate → 6Nolo=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.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionFind K Closest Elements
Next Question →Split Array Largest Sum