Capacity To Ship Packages Within D Days | Leetcode 1011

The “Capacity To Ship Packages Within D Days” problem is a classic binary search question that helps you practice optimization with constraints.

In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

Here’s the [Problem Link] to begin with.

Problem Statement

You are given an array weights where each element represents the weight of a package. You have D days to ship all the packages.
You must ship the packages in order (no reordering). Each day, you can ship as many packages as you want, as long as their total weight does not exceed the ship’s capacity.
Your task is to find the minimum ship capacity needed to ship all packages within D days.

Example 1

Input:
weights = [1], D = 5

Output:
15

Explanation:
A capacity of 15 allows the packages to be shipped in 5 days.

Example 2

Input:
weights = [1], D = 3

Output:
6

Explanation:
A capacity of 6 allows the packages to be shipped in 3 days.

Brute Force Solution (Try Every Possible Capacity)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Try Every Capacity:
   Try every possible ship capacity from the maximum single package weight to the sum of all package weights.
2. Check If It Meets the Days Constraint:
   For each capacity, simulate the shipping process and count how many days it would take.
3. Return the First Valid Capacity:
   The first capacity for which the total days is less than or equal to D is our answer.
4. Why does this work?
   We check every possible capacity, so we’re sure to find the minimum one that works.

This approach is easy to understand but not efficient for large inputs.

Code Implementation

from typing import List

class Solution:
    def find_days(self, weights, capacity):
        total_days = 1
        current_load = 0

        for weight in weights:
            if current_load + weight > capacity:
                total_days += 1
                current_load = 0
            current_load += weight

        return total_days

    def shipWithinDays(self, weights: List[int], days: int) -> int:
        start_weight = max(weights)            # Minimum possible capacity
        end_weight = sum(weights)              # Maximum possible capacity
        for w in range(start_weight, end_weight + 1):
            total_days_taken = self.find_days(weights, w)
            if total_days_taken <= days:       # Check if this capacity works
                return w                       # Return the minimum capacity found

Code Explanation

• For each capacity from the largest single package to the total weight, simulate the shipping process.
• Use the helper function find_days to count how many days are needed for a given capacity.
• Return the first capacity that allows all packages to be shipped within D days.

Dry Run

Input:
weights = [1], D = 5

• Try capacity = 10: Too many days needed.
• Try capacity = 15: Can ship in 5 days. Return 15.

Final Output:
15

Time and Space Complexity

• Time Complexity: O((sum(weights) – max(weights)) * n)
  For each capacity, we check all packages.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The brute force approach is simple and works for small inputs, but it’s too slow for large values.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search on Capacity:
   The answer lies between the largest single package and the total weight. Use binary search to find the minimum capacity.
2. Check If It Meets the Days Constraint:
   For each mid value (capacity), simulate the shipping process and count the days needed.
3. Adjust Search Window:
   • If the number of days is within D, try a smaller capacity.
   • If not, try a larger capacity.
4. Why does this work?
   The days needed function is monotonic: as the capacity increases, the days needed decreases. Binary search is perfect for this.

Code Implementation

from typing import List

class Solution:
    def find_days(self, weights, capacity):
        total_days = 1
        current_load = 0

        for weight in weights:
            if current_load + weight > capacity:
                total_days += 1
                current_load = 0
            current_load += weight

        return total_days

    def shipWithinDays(self, weights: List[int], days: int) -> int:
        low = max(weights)              # Minimum possible capacity
        high = sum(weights)             # Maximum possible capacity
        while low <= high:
            mid = (low + high) // 2
            numberOfDays = self.find_days(weights, mid)
            if numberOfDays <= days:
                high = mid - 1          # Try a smaller capacity
            else:
                low = mid + 1           # Need a larger capacity
        return low                      # The minimum capacity found

Code Explanation

• Use binary search between the largest package and the total weight.
• For each mid capacity, simulate the shipping process.
• If the number of days is within D, try a smaller capacity.
• If not, try a larger capacity.
• Return the minimum valid capacity found.

Dry Run

Input:
weights = [1], D = 5

• low = 10, high = 55
• mid = 32, days needed = 3 (try smaller, high = 31)
• mid = 20, days needed = 4 (try smaller, high = 19)
• mid = 14, days needed = 6 (too many days, low = 15)
• mid = 17, days needed = 5 (just right, try smaller, high = 16)
• mid = 15, days needed = 5 (just right, try smaller, high = 14)

Loop ends, answer is 15.

Time and Space Complexity

• Time Complexity: O(n * log(sum(weights) – max(weights)))
  Binary search on capacity, checking all packages for each guess.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The optimal solution is efficient and works well for large arrays and high values. It’s the best approach for interviews and practical use.

Final Thoughts

The “Capacity To Ship Packages Within D Days” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.