DSA-067 · FOCUSED PRACTICE

Capacity to Ship Packages Within D Days

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 8204 deterministic checks. Learner drafts are not executed.

Understand the problem

Find the minimum ship capacity needed to deliver all packages within the given number of days. Packages must be loaded in their original order, and each package stays whole.

weights is non-null with 0–100,000 entries, each 1–1,000,000,000; days is 1–100,000.
A day carries one contiguous run of remaining packages with total weight at most capacity. You may use fewer than days; no reordering or splitting. Empty input returns 0.
Return long and preserve input. Both total weight and minimum capacity can exceed int. Linear-capacity baseline is educational and tested only with small numeric spans.

Examples

Input: weights=[1,2,3,4,5,6,7,8,9,10], days=5
Output: 15
One valid partition is [1..5], [6,7], [8], [9], [10]; a smaller capacity cannot meet the same deadline.
Input: weights=[3,2,2,4,1,4], days=3
Output: 6
Partitions [3,2], [2,4], [1,4] fit; capacity 5 needs more days.
Input: weights=[1,2,3], days=5
Output: 3
Unused days are allowed; the largest package is still a lower bound.

Before you start

Feasibility predicates and first-true search
Contiguous ordered partitions and long sums

Recognize the structure

The answer is a number with a monotone predicate: once a capacity works, larger capacities also work. This is not searching a sorted input array. Feasibility requires an order-preserving greedy partition, not arbitrary bin packing.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 109/20,000 characters

Self-review

I can prove both greedy feasibility and monotonicity.I preserve order and allow unused days.I shrink inclusive bounds without losing the first feasible value.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Can increasing capacity ever make a feasible schedule impossible?

Hint 2

Test one capacity by filling each ordered day as far as it can go.

Hint 3

Binary-search the first feasible capacity between maximum weight and total.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Test every integer capacity

Try capacities from the heaviest package through total weight. Greedily fill each day until the next package would overflow. For [2,3,2] and two days, capacity 3 needs three days, capacity 4 still needs three, and capacity 5 works. If S is total and M is maximum, time is O(n(S-M+1)); even small n can be too slow when weights are large.

Improve the baseline

Bound the answer

No capacity below the maximum weight works, and total weight always works in one day. Accumulate both bounds in long.

Prove the daily packing test

Fill each day with the longest feasible prefix. No alternative can finish that day farther into the order; induction shows greedy uses the fewest days for a fixed capacity.

Keep the first feasible capacity

Use low<high and mid=low+(high-low)/2. A feasible mid moves high to mid; an infeasible mid moves low to mid+1. The optimum remains in the inclusive interval.

Why it is correct

Initialize

The optimum lies within [maxWeight,totalWeight]; for an empty input both are zero and the loop is skipped.

Preserve

The greedy checker correctly decides whether at most days suffice. Feasibility is monotone because a larger capacity can reuse every partition feasible at a smaller capacity. Thus each binary-search update removes only impossible answers or unnecessarily large candidates.

Finish

Each update strictly shrinks the integer interval. At low=high the only remaining candidate is the first feasible capacity and therefore the minimum.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    public static long shipWithinDays(int[] weights, int days) {
        long low = 0, high = 0;
        for (int weight : weights) { low = Math.max(low, weight); high += weight; }
        while (low < high) {
            long mid = low + (high - low) / 2;
            if (feasible(weights, days, mid)) high = mid;
            else low = mid + 1;
        }
        return low;
    }

    private static boolean feasible(int[] weights, int days, long capacity) {
        int used = 1;
        long load = 0;
        for (int weight : weights) {
            if (weight > capacity) return false;
            if (load + weight > capacity) { used++; load = 0; }
            load += weight;
        }
        return used <= days;
    }

    public static long baseline(int[] weights, int days) {
        long maximum = 0, total = 0;
        for (int weight : weights) { maximum = Math.max(maximum, weight); total += weight; }
        for (long capacity = maximum; capacity <= total; capacity++)
            if (feasible(weights, days, capacity)) return capacity;
        return 0;
    }
}

Read the meaningful blocks

Use long bounds and loads

Even when one package fits int, the total may not.

Split only on strict overflow

If load+weight equals capacity, the package belongs to the same day. Reset load before adding the first package of a new day.

Use at most days

used<=days permits unused days, including days greater than the number of packages.

Complexity

For nonempty input, O(n log(S-M+1)+n) time and O(1) auxiliary space, where S is total weight and M is maximum. Empty input takes O(1).

The linear-capacity baseline is O(n(S-M+1)) and O(1) workspace; this depends on the numeric answer range, not just n. Return and midpoint arithmetic use long.

Exact-state walkthroughs

Reveal normal and boundary traces

First feasible capacity

Input: {"weights":[2,3,2],"days":2} · Result: 5

Step 1 of 4: The answer lies between the maximum and total weight.

The inclusive interval contains the optimum.

State after this step
Variable	Value
weights	`[2,3,2]`
days	`2`
low	`3`
high	`7`

See the affected Java block

 1 public final class Solution {
 2     public static long shipWithinDays(int[] weights, int days) {
 3         long low = 0, high = 0;
 4         for (int weight : weights) { low = Math.max(low, weight); high += weight; }
 5         while (low < high) {
 6             long mid = low + (high - low) / 2;
 7             if (feasible(weights, days, mid)) high = mid;
 8             else low = mid + 1;
 9         }
10         return low;
11     }
12 
13     private static boolean feasible(int[] weights, int days, long capacity) {
14         int used = 1;
15         long load = 0;
16         for (int weight : weights) {
17             if (weight > capacity) return false;
18             if (load + weight > capacity) { used++; load = 0; }
19             load += weight;
20         }
21         return used <= days;
22     }
23 
24     public static long baseline(int[] weights, int days) {
25         long maximum = 0, total = 0;
26         for (int weight : weights) { maximum = Math.max(maximum, weight); total += weight; }
27         for (long capacity = maximum; capacity <= total; capacity++)
28             if (feasible(weights, days, capacity)) return capacity;
29         return 0;
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

The answer lies between the maximum and total weight.
The inclusive interval contains the optimum.
weights
[2,3,2]
days
2
low
3
high
7
Pack in order, test the midpoint, and shrink the interval.
Greedy packing minimizes days at mid; the optimum remains in [low,high].
before
[3,7]
mid
5
loads
[5,2]
neededDays
2
feasible
true
low
3
high
5
Pack in order, test the midpoint, and shrink the interval.
Greedy packing minimizes days at mid; the optimum remains in [low,high].
before
[3,5]
mid
4
loads
[2,3,2]
neededDays
3
feasible
false
low
5
high
5
Return the contract result.
The final state satisfies the requested output contract.
result
5

More days than packages

Input: {"weights":[5],"days":10} · Result: 5

Step 1 of 2: The answer lies between the maximum and total weight.

The inclusive interval contains the optimum.

State after this step
Variable	Value
weights	`[5]`
days	`10`
low	`5`
high	`5`

See the affected Java block

 1 public final class Solution {
 2     public static long shipWithinDays(int[] weights, int days) {
 3         long low = 0, high = 0;
 4         for (int weight : weights) { low = Math.max(low, weight); high += weight; }
 5         while (low < high) {
 6             long mid = low + (high - low) / 2;
 7             if (feasible(weights, days, mid)) high = mid;
 8             else low = mid + 1;
 9         }
10         return low;
11     }
12 
13     private static boolean feasible(int[] weights, int days, long capacity) {
14         int used = 1;
15         long load = 0;
16         for (int weight : weights) {
17             if (weight > capacity) return false;
18             if (load + weight > capacity) { used++; load = 0; }
19             load += weight;
20         }
21         return used <= days;
22     }
23 
24     public static long baseline(int[] weights, int days) {
25         long maximum = 0, total = 0;
26         for (int weight : weights) { maximum = Math.max(maximum, weight); total += weight; }
27         for (long capacity = maximum; capacity <= total; capacity++)
28             if (feasible(weights, days, capacity)) return capacity;
29         return 0;
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

The answer lies between the maximum and total weight.
The inclusive interval contains the optimum.
weights
[5]
days
10
low
5
high
5
Return the contract result.
The final state satisfies the requested output contract.
result
5

Test the contract

Input: weights=[], days=1
Output: 0
No packages.
Input: weights=[5], days=10
Output: 5
Largest package bound.
Input: weights=[2,3], days=1
Output: 5
Exact equality.
Input: weights=[1000000000,1000000000,1000000000], days=1
Output: 3000000000
Long total.

Common mistakes and counterexamples

Reorder packages

Counterexample: [3,2,2,4,1,4] is an ordered partition task.

Greedily consume the next package in sequence.

Require exactly days nonempty shipments

Counterexample: [1,2,3], days=5 is valid with capacity 3.

Accept at most days.

Lose equality at the boundary

Counterexample: [2,3], capacity 5 fits one day.

Split only when load+weight>capacity.

Follow-ups

Return the actual partition.

Run the greedy checker at the optimum and record boundaries. If exactly D nonempty days are required, validate D≤n and split feasible groups while reserving packages for remaining days.

Packages can be reordered.

The fixed-order greedy proof no longer applies; the task becomes a packing/partition variant. Do not retain the same predicate without a new correctness argument.

Minimize completion days for a fixed capacity.

The same greedy scan directly returns the fewest days; binary search is unnecessary. Reject a capacity smaller than any single package.

Related foundations

Binary search: candidate intervals and monotone feasibility

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-14 · Original explanations, examples, and Java implementations for AceYourInterviews. Familiar task names identify standard algorithmic problems; no company-frequency claims are made.