Log inSign up
mediumleetcodeNot Started

Capacity To Ship Packages Within D Days

A conveyor belt has packages that must be shipped within days days. Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Binary Search
Solve on leetcode
Lesson

Problem Statement

A conveyor belt has packages that must be shipped from one port to another within days days.\n\nThe i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.\n\nReturn the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Example 1 · Example 1: Standard Partition:

Input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all packages in 5 days: Day 1: [1,2,3,4,5] (15), Day 2: [6,7] (13), Day 3: [8] (8), Day 4: [9] (9), Day 5: [10] (10).

Example 2 · Example 2: Balanced Split:

Input: weights = [3, 2, 2, 4, 1, 4], days = 3
Output: 6
Explanation: Day 1: [3, 2] (5), Day 2: [2, 4] (6), Day 3: [1, 4] (5).

Example 3 · Example 3: Days Equal to Package Count:

Input: weights = [1, 2, 3, 1, 1], days = 4
Output: 3
Explanation: Day 1: [1], Day 2: [2], Day 3: [3], Day 4: [1, 1].

Constraints:

  • 1 <= days <= weights.length <= 5 * 104
  • 1 <= weights[i] <= 500

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize the equivalence between capacity shipping and minimax subarray sum partitioning.
  • Identify correct bounds: low = max(weights), high = sum(weights).
  • Implement greedy sequential packaging simulation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partition an array into k contiguous sub-segments to minimize the maximum sub-segment sum.
  • Monotonic capacity property.
  • Ship packages in strict given order.

Algorithmic Decision Tree:

  • low = max(weights), high = sum(weights), ans = high.
  • While low <= high: mid = low + (high - low) / 2.
  • Simulate packing with capacity mid:
  • - daysNeeded = 1, currWeight = 0.
  • - For w in weights: if currWeight + w > mid -> daysNeeded++, currWeight = 0; currWeight += w.
  • If daysNeeded <= days: ans = mid, high = mid - 1.
  • Else: low = mid + 1.
  • Return ans.

Connected Patterns:

Split Array Largest Sum (identical problem)Painter's Partition ProblemBook Allocation ProblemKoko Eating Bananas

1. Linear Capacity Increment

Intuition

Start cap at max(weights). For each cap, simulate greedy packing. Return the first cap where daysNeeded <= days.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: low = max(weights), high = sum(weights).
  2. Step 2: Loop cap from low to high.
  3. Step 3: Simulate packing: count daysNeeded.
  4. Step 4: If daysNeeded <= days, return cap.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int shipWithinDays(vector<int>& weights, int days) {
10 int maxW = 0, sumW = 0;
11 for (int w : weights) {
12 maxW = max(maxW, w);
13 sumW += w;
14 }
15 for (int cap = maxW; cap <= sumW; ++cap) {
16 int daysNeeded = 1, current = 0;
17 for (int w : weights) {
18 if (current + w > cap) {
19 daysNeeded++;
20 current = 0;
21 }
22 current += w;
23 }
24 if (daysNeeded <= days) return cap;
25 }
26 return sumW;
27 }
28};
29
30int main() {
31 // Sample driver execution
32 cout << "Execution completed successfully." << endl;
33 return 0;
34}
35

Time & Space Complexity

  • Time complexity: O(n * (sum(weights) - max(weights))) — Tests up to 500 * 50000 = 2.5 * 107 capacities with O(n) simulation each, causing TLE.
  • Space complexity: O(1) — O(1) auxiliary space.

2. Lower Bounded Linear Search with Jump Steps

Intuition

Mathematically, the ship must have capacity >= ceil(sum(weights) / days). Starting from max(maxW, ceil(sum/days)) reduces iterations.

When to apply: When search range is small.

Algorithm

  1. Step 1: Compute maxW = max(weights) and sumW = sum(weights).
  2. Step 2: Start cap = max(maxW, (sumW + days - 1) / days).
  3. Step 3: Test cap sequentially until daysNeeded <= days.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int shipWithinDays(vector<int>& weights, int days) {
10 int maxW = 0, sumW = 0;
11 for (int w : weights) {
12 maxW = max(maxW, w);
13 sumW += w;
14 }
15 int startCap = max(maxW, (sumW + days - 1) / days);
16 for (int cap = startCap; cap <= sumW; ++cap) {
17 int daysNeeded = 1, current = 0;
18 for (int w : weights) {
19 if (current + w > cap) {
20 daysNeeded++;
21 current = 0;
22 }
23 current += w;
24 }
25 if (daysNeeded <= days) return cap;
26 }
27 return sumW;
28 }
29};
30
31int main() {
32 // Sample driver execution
33 cout << "Execution completed successfully." << endl;
34 return 0;
35}
36

Time & Space Complexity

  • Time complexity: O(n * (sumW - sumW/days)) — Linear in remaining capacity range.
  • Space complexity: O(1) — O(1) memory.

3. Binary Search on Capacity (Search on Answer)

Intuition

Initialize low = max(weights), high = sum(weights), ans = high. While low <= high, compute mid. Simulate greedy packing: if currentDayWeight + w > mid, increment day count and reset currentDayWeight = w. If total days <= days, record ans = mid and search left (high = mid - 1); else search right (low = mid + 1).

When to apply: Standard optimal solution.

Algorithm

  1. Step 1: low = max(weights), high = sum(weights), ans = high.
  2. Step 2: While low <= high:
  3. - mid = low + (high - low) / 2.
  4. - daysNeeded = 1, current = 0.
  5. - For w in weights: if (current + w > mid) { daysNeeded++; current = 0; } current += w.
  6. - If daysNeeded <= days: ans = mid, high = mid - 1.
  7. - Else low = mid + 1.
  8. Step 3: Return ans.

Trace for weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Range [10, 55]
Visual state
Values and pointers at this exact step
pointers
S
8 days
5 days
2 days
1 day
0
↑ low
1
2
↑ mid
3
↑ high
Check / comparison
At capacity 32, days needed = 2 <= 5 -> Feasible.
Decision / next transition
Record ans = 32, set high = 31.
Why this step matters

Range [10, 55]. mid=32. Pack with capacity 32: Day 1: [1..7] (28), Day 2: [8..10] (27) -> 2 days <= 5. Valid! ans=32. Search left: high = mid - 1 = 31.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int shipWithinDays(vector<int>& weights, int days) {
10 int low = 0, high = 0;
11 for (int w : weights) {
12 low = max(low, w);
13 high += w;
14 }
15
16 int ans = high;
17 while (low <= high) {
18 int mid = low + (high - low) / 2;
19 int daysNeeded = 1, current = 0;
20 for (int w : weights) {
21 if (current + w > mid) {
22 daysNeeded++;
23 current = 0;
24 }
25 current += w;
26 }
27 if (daysNeeded <= days) {
28 ans = mid;
29 high = mid - 1;
30 } else {
31 low = mid + 1;
32 }
33 }
34 return ans;
35 }
36};
37
38int main() {
39 // Sample driver execution
40 cout << "Execution completed successfully." << endl;
41 return 0;
42}
43

Time & Space Complexity

  • Time complexity: O(n * log(sum(weights) - max(weights))) — Search space [max, sum] is at most 2.5 * 107, requiring at most 25 binary search steps. Each step takes O(n) to greedily simulate.
  • Space complexity: O(1) — Operates in O(1) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Capacity IncrementO(n * range)O(1)Test each capacity from max to sum.Inspects every single capacity.
2.Bounded Linear SearchO(n * range)O(1)Start from max(maxW, sumW/days).Linear stepping.
3.Binary Search on AnswerOptimalO(n * log(range))O(1)Binary search on monotonic capacity domain [max, sum].None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • days == 1 -> capacity must equal sum(weights).
  • days == weights.length -> capacity equals max(weights).
  • Single package: weights = [500], days = 1 -> return 500.
  • All weights identical.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explicitly mention that this problem is mathematically identical to 'Split Array Largest Sum' and Painters Partition Problem'.
  2. Explain why the lower bound cannot be less than max(weights).
  3. Demonstrate why greedy packing is optimal (delaying a ship load never helps).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why cannot the lower bound of binary search be 1 or 0?

Back to DSA Sheet