Capacity to Ship Packages Within D Days — Binary Search on Answer [LC 1011, Amazon]

Problem Statement#

A conveyor belt has packages with weights weights[i]. Each day you load packages onto the ship in order (cannot split a package). Find the minimum weight capacity to ship all packages within days days.

Constraints:

• 1 <= days <= weights.length <= 5 * 10^4
• 1 <= weights[i] <= 500

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

Input:  weights = [3,2,2,4,1,4], days = 3
Output: 6

Why This Problem Matters#

LC 1011 is the most straightforward example of the "binary search on the answer" template and is frequently asked by Amazon in online assessments. The problem looks like an optimisation problem, but once you recognise that feasibility is monotone — higher capacity always makes it easier or equally easy to meet the deadline — binary search applies directly.

This problem is structurally identical to LC 875 (Koko Eating Bananas), LC 1482 (Minimum Days to Make Bouquets), and LC 410 (Split Array Largest Sum). Mastering the feasibility-check pattern here transfers to all of them.

The search bounds are the critical insight: the minimum possible capacity is max(weights) (must carry the heaviest package), and the maximum needed is sum(weights) (carry everything in one day).

The Core Insight#

Binary search on capacity c in [max(weights), sum(weights)]. For a given capacity c, greedily simulate: load packages in order, starting a new day whenever adding the next package would exceed c. Count the days needed. If days needed <= D, capacity c is feasible.

Feasibility is monotone: if capacity c works, any capacity > c also works. This means there is a threshold — the minimum feasible capacity — and binary search finds it in O(log(sum - max)) iterations.

Visual Dry Run#

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

Wait — let me re-verify: at capacity 15, days needed: [1+2+3+4+5=15], [6+7=13], [8], [9], [10] = 5 days. Correct, output is 15.

Solution (Optimal)#

class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def feasible(capacity: int) -> bool:
            day_count, current = 1, 0
            for w in weights:
                if current + w > capacity:
                    day_count += 1
                    current = 0
                current += w
            return day_count <= days
 
        lo, hi = max(weights), sum(weights)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if feasible(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

var shipWithinDays = function(weights, days) {
    function feasible(capacity) {
        let dayCount = 1, current = 0;
        for (const w of weights) {
            if (current + w > capacity) {
                dayCount++;
                current = 0;
            }
            current += w;
        }
        return dayCount <= days;
    }
 
    let lo = Math.max(...weights);
    let hi = weights.reduce((a, b) => a + b, 0);
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
};

Time: O(n log(sum - max)) — O(log S) iterations, each O(n) greedy check Space: O(1) — only counter variables in the feasibility check

Common Mistakes#

• Setting lo = 0 or lo = 1 — the minimum capacity must be max(weights) or the heaviest package cannot be shipped at all.
• Setting hi = max(weights) — the upper bound must be sum(weights) to cover the case where everything ships in one day.
• Off-by-one in the feasibility check: counting days as 0 and not incrementing at the start — initialise day_count = 1 and current = 0.
• Using mid = (lo + hi) // 2 in languages with 32-bit integer overflow — prefer lo + (hi - lo) // 2.
• Forgetting the feasible check uses <= days, not < days.

Interview Tips#

• State the search bounds before writing any code: "minimum is max(weights), maximum is sum(weights)."
• Write the feasible helper as a separate function — it makes the binary search loop clean and the logic easy to verify.
• Mention the generalisation: this exact template solves any "find minimum X such that greedy-check(X) passes" problem.
• The feasibility check is a greedy simulation — emphasise that you are NOT using DP here.

Follow-up Questions#

• LC 875 (Koko Eating Bananas): Same template. Search speed in [1, max(piles)], feasibility checks total hours.
• LC 1482 (Minimum Days to Make Bouquets): Search days, feasibility counts consecutive bloomed flowers.
• LC 410 (Split Array Largest Sum): Search max subarray sum, feasibility counts needed splits. Identical greedy check.
• What if packages can be reordered? Sort in descending order to minimise wasted capacity per day — but the constraint says packages must ship in order, so reordering is not allowed.
• What if there are weight limits per item? No change to the binary search; the feasibility check already handles each item individually.

Key Takeaways#

• LC 1011 is the most direct application of the binary search on answer template: search capacity in [max(weights), sum(weights)].
• The search bounds have clear physical meaning: minimum must carry the heaviest package, maximum carries all at once.
• The feasibility check is a greedy O(n) simulation: greedily pack packages, starting new days when capacity is exceeded.
• Use while lo < hi with hi = mid on success and lo = mid + 1 on failure — the loop exits at the minimum feasible capacity.
• This problem is structurally identical to LC 875, LC 1482, and LC 410 — master this one and you have the template for all.
• Time complexity O(n log S) where S = sum(weights): the log factor comes from binary search, not the greedy check.
• Amazon asks this problem frequently in online assessments and phone screens as a test of the binary-search-on-answer pattern.