medium Capacity To Ship Packages Within D Days

Problem Statement

You are given weights array of size n, where weights[i] represents the weight of the i^th package. These n packages should be shipped from one place to another place via one ship within a given days.

If you can load the ship with some packages each day (in the order given in weights[i]), find the smallest possible maximum weight the ship can carry per day without exceeding the given number of days for shipping all packages.

Examples

Example 1:

Input: weights = [10,20,30,40,50], days = 3
Expected Output: 60
Justification: A capacity of 60 means shipping [10,20,30] on day 1, [40] on day 2, and [50] on day 3.

Example 2:

Input: weights = [5,5,5,5,5,5,5,5,5,5], days = 5
Expected Output: 10
Justification: A capacity of 10 allows shipping two packages of weight 5 each day, perfectly fitting within 5 days.

Example 3:

Input: weights = [4, 8, 5, 2, 6, 3, 7, 9], days = 4
Expected Output: 13
Justification: A capacity of 13 allows shipping [4, 8] on day 1 (total 12, close to 13 without exceeding), [5, 2, 6] on day 2 (total 13), [3, 7] on day 3 (total 10), and [9] on day 4.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Capacity To Ship Packages Within D Days — problem

0. Pattern family

Family: Binary search on the answer + linear feasibility

1. Why / judgment (K3)

Monotone: larger capacity ⇒ fewer days needed. Low=max(weights), high=sum(weights); mid capacity feasible if greedy pack days ≤ D. Canonical “BS on answer” company problem.

2. Worked complexity / derivation (K11)

Feasibility O(n) per mid. log(sum) mids → O(n log S), S=sum weights.

3. Pattern + recognition + when-NOT (K12)

Name: BINARY SEARCH ON CAPACITY

Recognition: min max-load / capacity with day limit; packages order fixed.

When-NOT: Reorder packages → bin packing NP-hard. Split array largest sum — same pattern different story.

4. Edge hand-run (K13)

weights=[1,2,3,4,5,6,7,8,9,10] D=5 →15 classic. D=1 →sum. D=n →max weight.

5. Interviewer follow-ups & drills

Q1. Why lo=max(w)?
Model answer: Single package cannot split; capacity ≥ heaviest.

Q2. Feasibility fn?
Model answer: Greedy left-to-right fill; count days.

Q3. Off-by-one lo/hi?
Model answer: while lo<hi; if ok hi=mid else lo=mid+1.

✅ Solution Capacity To Ship Packages Within D Days

Problem Statement

Examples

Example 1:

Input: weights = [10,20,30,40,50], days = 3
Expected Output: 60
Justification: A capacity of 60 means shipping [10,20,30] on day 1, [40] on day 2, and [50] on day 3.

Example 2:

Input: weights = [5,5,5,5,5,5,5,5,5,5], days = 5
Expected Output: 10
Justification: A capacity of 10 allows shipping two packages of weight 5 each day, perfectly fitting within 5 days.

Example 3:

Input: weights = [4, 8, 5, 2, 6, 3, 7, 9], days = 4
Expected Output: 13
Justification: A capacity of 13 allows shipping [4, 8] on day 1 (total 12, close to 13 without exceeding), [5, 2, 6] on day 2 (total 13), [3, 7] on day 3 (total 10), and [9] on day 4.

Solution

To solve this problem, we'll use a binary search approach. This method is effective because it efficiently narrows down the minimum capacity required. We know that the minimum capacity must be at least the weight of the heaviest package and at most the sum of all package weights. We'll use these as our initial bounds for binary search.

In each iteration, we'll calculate the mid-value between our bounds and check if it's possible to ship all packages within the given days using this capacity. If it's possible, we try to find a smaller capacity by adjusting our upper bound. If it's not possible, we increase our lower bound. This approach ensures we find the smallest capacity that still allows all packages to be shipped within the given timeframe.

Step-by-step Algorithm

Initialize Bounds: Set the lower bound (left) to the maximum weight in the array and the upper bound (right) to the sum of all weights.
Binary Search:
- While left is less than right, do the following:
  - Find the midpoint (mid) between left and right. This represents the current guess for the shipping capacity.
  - Initialize two variables, need (starting at 1, representing the number of days needed) and cur (current weight for the day, starting at 0).
Check Feasibility:
- Iterate over the weights array. For each weight w:
  - If cur + w is greater than mid, increment need by 1 (indicating an additional day is needed) and reset cur to 0.
  - Add w to cur.
- After iterating through all weights, check if need is greater than D. If so, it means the current capacity mid is too low, and we need to increase left to mid + 1. Otherwise, set right to mid.
Find Minimum Capacity: The loop continues until left meets right. The value of left at the end of the binary search is the minimum capacity required to ship all packages within D days.

Algorithm Walkthrough

Let's consider the input: weights = [4, 8, 5, 2, 6, 3, 7, 9], days = 4

Initialization:
- left = 9, right = 44.
First Iteration:
- mid = (9 + 44)/2 = 26.
- Day 1: Ship 4, 8, 5, 2, 6 (total 25) - under capacity.
- Day 2: Ship 3, 7 (total 10) - under capacity.
- Day 3: Ship 9 (total 9) - under capacity.
- Ships in 3 days, feasible. Set right to 26.
Second Iteration:
- mid = (9 + 26)/ 2 = 17.
- Day 1: Ship 4, 8, 5 (total 17) - under capacity.
- Day 2: Ship 2, 6, 3 (total 11) - under capacity.
- Day 3: Ship 7 (total 7) - under capacity.
- Day 4: Ship 9 (total 9) - under capacity.
- Ships in 4 days, feasible. Set right to 17.
Third Iteration:
- mid = (9 + 17)/2 = 13.
- Day 1: Ship 4, 8 (total 12) - under capacity.
- Day 2: Ship 5, 2, 6 (total 13) - under capacity.
- Day 3: Ship 3, 7 (total 10) - under capacity.
- Day 4: Ship 9 (total 9) - under capacity.
- Ships in 4 days, feasible. Set right to 13.
Fourth Iteration:
- mid = (9 + 13)/2 = 11.
- Day 1: Ship 4 (total 4) - under capacity.
- Day 2: Ship 8 (total 8) - under capacity.
- Day 3: Ship 5, 2 (total 7) - under capacity.
- Day 4: Ship 6, 3 (total 9) - under capacity.
- Day 5: Ship 7 (total 7) - under capacity.
- Day 6: Ship 9 (total 9) - under capacity.
- It ships in 6 days, which is not feasible. Set left to 12.
Fifth Iteration:
- mid = (12 + 13)/2 = 12.
- Day 1: Ship 4, 8 (total 12) - under capacity.
- Day 2: Ship 5, 2 (total 7) - under capacity.
- Day 4: Ship 6, 3 (total 9) - under capacity.
- Day 5: Ship 7 (total 7) - under capacity.
- Day 6: Ship 9 (total 9) - under capacity.
- It ships in 5 days, which is not feasible. Set left to 13.
Continue Iterations:
- left >= right, break the loop.
Final Output:
- The loop ends with left = 13, which is the minimum capacity needed.

Code

java

public class Solution {

  public int shipWithinDays(int[] weights, int D) {
    // Initialize the lower and upper bounds
    int left = 0, right = 0;
    for (int w : weights) {
      left = Math.max(left, w); // Lower bound is the max weight
      right += w; // Upper bound is the sum of all weights
    }

    // Binary search to find the minimum capacity
    while (left < right) {
      int mid = (left + right) / 2; // Calculate the middle value
      int need = 1, cur = 0; // Variables to track the number of days and current weight

      // Check if it's possible to ship all packages within D days using the mid capacity
      for (int w : weights) {
        if (cur + w > mid) {
          need += 1; // Increment the day count if current weight exceeds mid capacity
          cur = 0; // Reset current weight
        }
        cur += w; // Add weight to current
      }

      // Adjust the search bounds based on the feasibility
      if (need > D) left = mid + 1; // Increase lower bound if more days are needed
      else right = mid; // Decrease upper bound if it's feasible
    }

    return left; // The minimum capacity required
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] weights1 = { 10, 20, 30, 40, 50 };
    int days1 = 3;
    System.out.println(
      "Example 1: " + solution.shipWithinDays(weights1, days1)
    ); // Expected output: 60

    // Example 2
    int[] weights2 = { 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 };
    int days2 = 5;
    System.out.println(
      "Example 2: " + solution.shipWithinDays(weights2, days2)
    ); // Expected output: 10

    // Example 3
    int[] weights3 = { 4, 8, 5, 2, 6, 3, 7, 9 };
    int days3 = 4;
    System.out.println(
      "Example 3: " + solution.shipWithinDays(weights3, days3)
    ); // Expected output: 13
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is O(N * log(S)) where N is the size of the weights array, and S is sum of all package weights.

The binary search runs in logarithmic time, so its time complexity is O(log(S)), where S is the sum of weights. For each iteration of the binary search, the algorithm iterates through the array once, which takes O(N) time. Thus, the overall time complexity is O(N * log(S)).

Space Complexity

The algorithm uses only a constant amount of extra space for variables, irrespective of the input size. The space used for input (weights array) is not considered in space complexity analysis. Thus, the space complexity is constant, O(1).

🎯 STRICT STANDOUT — Solution Capacity To Ship Packages Within D Days

0. Pattern family

Family: Binary search on answer + greedy pack

1. Why / judgment (K3)

Implement feasible(cap): walk weights, reset day load. BS lo/hi as above. Hand-trace off-by-one on lo/hi convergence.

2. Worked complexity / derivation (K11)

O(n log S) time, O(1) extra space.

3. Pattern + recognition + when-NOT (K12)

Name: BS-ON-ANSWER CAPACITY

Recognition: min capacity ship in ≤D days order-preserving.

When-NOT: freestyle reordering. Multiple ships parallel — different.

4. Edge hand-run (K13)

D=5 weights 1..10 →15. Verify feasible(14) false, feasible(15) true.

5. Interviewer follow-ups & drills

Q1. Why monotone?
Model answer: If cap works, cap+1 works.

Q2. days count init?
Model answer: days=1 load=0; if load+w>cap days++ load=w.

Q3. Return lo or hi?
Model answer: After lo==hi both answer.

🧩 Pattern · Binary Search

Recognize it: Sorted input (or a monotonic answer space) + “find / minimise / smallest-x-such-that” → halve the range each step.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Capacity To Ship Packages Within D Days? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Capacity To Ship Packages Within D Days** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Capacity To Ship Packages Within D Days** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Capacity To Ship Packages Within D Days**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Capacity To Ship Packages Within D Days**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Maximum Product Subarray Best Time to Buy and Sell Stock II →