Capacity To Ship Packages Within D Days

You run a super busy delivery company.

Your mission? Ship a bunch of packages within D days.

There’s one catch: You can’t just use any truck. Each truck has a maximum weight capacity, and you need to figure out the smallest capacity that still gets the job done on time.

Sounds simple, right?

Well, there’s a bit of strategy involved — and we’re going to use Binary Search to make it easier!

Breaking Down the Puzzle 📦

Let’s look at the setup:

You have 10 packages with the following weights:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

You need to ship all of them in D = 5 days.

So, how do you figure out the minimum truck capacity to do this?

🤔 The Options:

• Option 1: Load just one package per day. Super safe… but very slow and wasteful.
• Option 2: Load each day up to the maximum the truck can carry. But how much is too much?

That’s where Binary Search saves the day!

Why Use Binary Search? 🎯

Binary search helps you find the middle ground quickly. Imagine you’re playing a guessing game where you keep narrowing down your options until you find the best one.

Here’s the plan:

1. Define the Search Range:

• Left boundary = the weight of the heaviest package (you can’t carry less than that)
• Right boundary = sum of all weights (if you did it all in one day)

2. Guess a Midpoint:

• Try a middle value as capacity.
• Simulate shipping. If it works within D days, maybe you can go lower.
• If not, you need to increase the capacity.

The Code — Let’s Ship This! 🛳️

Here’s the code to solve the problem:

class Solution {

public int shipWithinDays(int[] weights, int D) {

int left = 0, right = 0;

// Step 1: Set left to the heaviest package and right to total weight

for (int weight : weights) {

left = Math.max(left, weight); // The heaviest package is the minimum capacity

right += weight; // The sum of all weights is the max possible capacity

}

// Step 2: Apply binary search

while (left < right) {

int mid = left + (right - left) / 2;

int daysRequired = 1; // Start counting days from 1

int currentLoad = 0; // Current load of the ship

// Step 3: Check how many days it takes to ship with the mid capacity

for (int weight : weights) {

if (currentLoad + weight > mid) {

daysRequired++; // Start a new day if the ship can't carry more

currentLoad = 0; // Reset current load

}

currentLoad += weight; // Add the current package to the load

}

// Step 4: Adjust binary search based on the number of days required

if (daysRequired > D) {

left = mid + 1; // If it took more than D days, increase capacity

} else {

right = mid; // If within D days, try a smaller capacity

}

}

return left; // The optimal capacity is found when left == right

}

}

How the Binary Search Works 🔍

🛠️ Step-by-step Strategy:

1. Start with a Range:

• The smallest possible ship capacity is the weight of the heaviest package (because the ship has to carry at least that much).

left = max(weights)

• The largest possible capacity is the total weight of all the packages (meaning you could theoretically fit everything in one ship).

right = sum(weights)

2. Midpoint Guess:

• You start by guessing a middle capacity and see if it can ship everything in D days.
• If the ship can’t handle it, increase the capacity.
• If the ship can handle it, try a smaller capacity and check again.

📊 Time & Space Complexity

1. Time Complexity: O(n * log(sum - max))

• For each binary search guess, we simulate a shipping plan in O(n)

2. Space Complexity: O(1)

• No extra memory used apart from a few tracking variables

🚚 Example Walkthrough — Let’s Ship It, Step by Step!

Let’s say we have the following:

• weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
• D = 5 (we need to ship all packages within 5 days)

⏱ Step 1: Binary Search Range

• Left = max weight = 10 (because the ship has to carry at least the heaviest package)
• Right = total weight = 55 (if we ship everything in one day)

So our search range is from 10 to 55.

🔍 Step 2: Start the Binary Search

We try the midpoint capacity each time and simulate how many days it would take to ship everything.

⛴️ First Try: mid = (10 + 55) / 2 = 32

Simulate shipping:

• Day 1: 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

→ Next package (8) would make it 36 > 32, so start Day 2

• Day 2: 8 + 9 = 17

→ Next package (10) would make it 27 → still within 32

• Day 3: 10

🧮 Total days: 3 days ✅ → Valid, but can we try a smaller capacity?

🔁 Update: right = 32

⛴️ Second Try: mid = (10 + 32) / 2 = 21

Simulate shipping:

• Day 1: 1 + 2 + 3 + 4 + 5 + 6 = 21

→ Next package is 7 → too much for Day 1

• Day 2: 7 + 8 = 15
• Day 3: 9
• Day 4: 10

🧮 Total days: 4 days ✅ → Still valid, try smaller

🔁 Update: right = 21

⛴️ Third Try: mid = (10 + 21) / 2 = 15

Simulate shipping:

• Day 1: 1 + 2 + 3 + 4 + 5 = 15
• Day 2: 6 + 7 = 13
• Day 3: 8
• Day 4: 9
• Day 5: 10

🧮 Total days: 5 days ✅ → Still valid, try smaller

🔁 Update: right = 15

⛴️ Fourth Try: mid = (10 + 15) / 2 = 12

Simulate shipping:

• Day 1: 1 + 2 + 3 + 4 = 10
• Day 2: 5 + 6 = 11
• Day 3: 7
• Day 4: 8
• Day 5: 9
• Day 6: 10

🧮 Total days: 6 days ❌ → Too many

🔁 Update: left = 13

⛴️ Fifth Try: mid = (13 + 15) / 2 = 14

Simulate shipping:

• Day 1: 1 + 2 + 3 + 4 = 10
• Day 2: 5 + 6 = 11
• Day 3: 7
• Day 4: 8
• Day 5: 9
• Day 6: 10

🧮 Total days: 6 days ❌ → Too many

🔁 Update: left = 15

Now left == right == 15 → That’s your minimum required capacity.

✅ Final Answer: 15

This is the smallest capacity that allows you to ship all the packages within 5 days.

📦 Key Takeaways

✅ Binary Search on Answer is perfect when you're finding the min/max value that satisfies a condition — even if the input isn’t sorted.

✅ Turn the problem into a YES/NO question:

“Can we ship all packages within D days using capacity C?”

✅ Use a greedy simulation to check a capacity guess:

• If the number of days exceeds D → increase capacity.
• If it's less or equal → try smaller.

✅ Binary Search Range:

• Left = max weight
• Right = total weight

✅ Time Complexity: O(n * log(sum - max))

✅ Space Complexity: O(1)