1011. Capacity To Ship Packages Within D Days

MediumArrayBinary Search
Leetcode Link

Problem Description

In this problem, we are tasked with finding the minimum weight capacity of a ship that is required to ship all packages on a conveyor belt within a specified number of days. Each package has a certain weight, and the ship cannot carry more than its maximum weight capacity. Therefore, the goal is to determine the smallest maximum weight that the ship can handle such that all the packages can still be shipped on time.

To accomplish this task, the packages must be loaded onto the ship in the same order as they are placed on the conveyor belt. This restriction adds complexity since we cannot reorder the packages to better fit the ship's weight capacity on a given day. Additionally, there is a limit to the number of days available to ship all packages.

Put simply, we need to discover the lightest possible maximum weight of the ship that allows all packages to be shipped within the given time frame. This weight determines how many packages can be loaded each day without exceeding the ship's weight limit, thus ensuring timely delivery.

Intuition

The solution to this problem relies on binary search, an efficient algorithm for finding an item in a sorted array. However, the direct application is not obvious because the weights are not sorted, and we are also dealing with an optimization problem, not just a simple search.

We use binary search to narrow down the possible range of the ship's weight capacity. The intuition here is that there is a lower bound, which is at least as large as the heaviest package (since the ship must be able to carry the heaviest package), and an upper bound, which is the sum of all package weights (since the ship can carry all packages at once).

The binary search will repeatedly split the range in half. At each step, it will guess a middle value and use a helper function check to determine if it is possible to ship all packages within 'days' days, without exceeding the guess weight capacity. The helper function will simulate the process of loading packages onto the ship:

  • It sums the weights of the packages until adding another package would exceed the assumed maximum capacity.
  • When the maximum is reached, it simulates the start of a new day, incrementing a day counter.
  • If the day counter exceeds the allowed number of days, the guess is too low and we must try a larger capacity.

The binary search is constrained within the range between the heaviest package and the total weight using the bisect_left function. bisect_left will find the position to insert the lower bound of the ship's capacity in such a way that all packages are shipped within the time frame. At the end of the binary search, the minimum weight capacity of the ship is found, which is the goal of the problem.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Solution Approach

The solution approach revolves around binary search, and here's a step-by-step breakdown of how the provided solution in Python implements it:

  1. Define the check Function:

    • The helper function check(mx) simulates the loading of packages onto the ship to determine if it is possible to ship all packages within days days, given a maximum shipping weight of mx.
    • It iterates through each weight in weights and aggregates them until the current load exceeds mx.
    • Once the aggregated weight exceeds mx, it simulates starting a new day by resetting the load to the current weight and incrementing the day count.
    • After iterating through all weights, if the number of days needed is less than or equal to days, it means the mx is a viable capacity; otherwise, it is not.

  2. Determine the Search Range:

    • The lower bound left is set to the maximum single package weight (max(weights)). This is the absolute minimum capacity the ship must have to ensure even the heaviest package can be shipped.
    • The upper bound right is set to the sum of all weights plus one (sum(weights) + 1), the plus one being a non-inclusive upper bound for the binary search.

  3. Perform Binary Search:

    • bisect_left function is used to perform the binary search. This is a function provided by Python's standard library, which uses binary search to find the insertion point for a given element x in a sorted array to maintain the array's sorted order. Here, it's used to find the minimum valid capacity.
    • The range from left to right is provided along with a key function check which bisect_left uses to determine the validity of the capacity. True represents the element to be inserted, corresponding to the condition of finding a workable capacity.

  4. Return the Calculated Capacity:

    • The minimum weight capacity is found when bisect_left concludes the search. It's computed as left + position where position is the insertion point returned by bisect_left. Since left is the starting point of the search range, adding the position gives us the exact weight capacity.

By leveraging binary search, the solution minimizes the number of times it needs to check for a viable shipping plan, which drastically reduces the time complexity compared to linearly searching through all possible capacities. The use of bisect_left provides a concise and efficient way to perform the search. The check function acts as a simulation/verification step that guarantees that the found capacity is indeed the lowest that can still ship all packages within the provided number of days.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

Let's assume we have the following input where weights = [3, 2, 2, 4, 1] represent the weights of the packages, and we need to ship all packages within days = 3.

We first determine the search range for the ship's capacity:

  • The heaviest package is 4, so our lower bound left is 4.
  • The sum of all package weights is 3+2+2+4+1 = 12, so our upper bound right is 13 (one more than the sum for binary search).

Now, we apply the binary search approach:

  1. We start with the middle of our range. The initial guess for the ship's capacity will be (left + right) / 2 which is (4 + 13) / 2 = 8.5. We round this down to 8 (since ship capacity must be an integer and binary search takes the lower mid).

  2. With a capacity of 8, we simulate the loading using the check function:

    • Day 1: We load 3 + 2 + 2 because adding the next package would exceed the capacity.
    • Day 2: We start with the next package and load 4.
    • Day 3: The last package 1 is loaded.

    We managed to load all the packages in 3 days which is within our allowed days. This indicates capacity 8 is possible.

  3. Since 8 worked, we now try to find if there is a smaller possible capacity. We adjust our search range to left remaining 4 and right becoming the current guess 8.

  4. Repeat the binary search process:

    • New middle is (4 + 8) / 2 = 6. So we check capacity 6.
    • Day 1: We load 3 + 2 because adding another package would exceed the capacity.
    • Day 2: We continue with 2 + 4, we reach the capacity exactly.
    • Day 3: We load the last package 1.

    Again, we have managed to load all the packages in 3 days, so capacity 6 seems to work as well.

  5. We continue the binary search with the new range left is 4 and right is now 6.

  6. New middle is (4 + 6) / 2 = 5. So we check capacity 5.

    • Day 1: We load 3 and cannot add 2 because it would exceed capacity, so we load just 3.
    • Day 2: We load 2 + 2 and stop there, as adding 4 would exceed the capacity.
    • Day 3: We load 4, but now we cannot load the last package as it would require an additional day.

    In this case, we failed to load all packages within 3 days using capacity 5. This tells us the capacity of 5 is too low.

  7. Now adjust the range with left becoming 6, since 5 didn't work, and right staying 6.

    Given that left and right are now the same, the search ends, and we have found that the minimum capacity needed is 6.

By using binary search and simulating the loading of packages, we determined that the minimum capacity of the ship to load all the packages within 3 days is 6. This approach is efficient because instead of trying every capacity between the heaviest package and the total weight, we eliminate half of the possibilities with each step.

Solution Implementation

1from typing import List
2from bisect import bisect_left
3
4class Solution:
5    def shipWithinDays(self, weights: List[int], days: int) -> int:
6        # Helper function to check if the given capacity 'max_capacity' is enough
7        # to ship all the packages within 'days' days
8        def can_ship_with_capacity(max_capacity):
9            current_weight, day_count = 0, 1  # Initialize current total weight and day count
10            # Loop through the weights of the packages
11            for weight in weights:
12                current_weight += weight  # Add package weight to current load
13                # If the current load exceeds the max capacity, start a new day
14                # and reset the current load to the current package's weight
15                if current_weight > max_capacity:
16                    day_count += 1
17                    current_weight = weight
18            # The capacity is enough if we can ship within required days
19            return day_count <= days
20
21        # Define the search space between largest single package and total weight
22        left, right = max(weights), sum(weights)
23      
24        # Use binary search to find the minimum capacity needed to ship within 'days' days
25        # The search will find the first value where 'can_ship_with_capacity' returns True
26        min_capacity_needed = left + bisect_left(range(left, right), True, key=can_ship_with_capacity)
27      
28        return min_capacity_needed
29
30# Example usage:
31# solution = Solution()
32# min_capacity = solution.shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)
33# print(min_capacity)  # Output: 15
34
1class Solution {
2    public int shipWithinDays(int[] weights, int days) {
3        // Setting initial left boundary to the largest weight 
4        // and right boundary to the sum of all weights
5        int leftBoundary = 0, rightBoundary = 0;
6        for (int weight : weights) {
7            leftBoundary = Math.max(leftBoundary, weight);
8            rightBoundary += weight;
9        }
10      
11        // Binary search to find the minimum capacity of the ship that will work within given days
12        while (leftBoundary < rightBoundary) {
13            // Midpoint to test if it's a valid ship capacity
14            int midCapacity = (leftBoundary + rightBoundary) >> 1;
15            // Check if midCapacity is enough, if so, look for a smaller potential capacity
16            if (canShip(weights, midCapacity, days)) {
17                rightBoundary = midCapacity;
18            } else {
19                // Otherwise, discard midCapacity and look for a larger one
20                leftBoundary = midCapacity + 1;
21            }
22        }
23        // Return the minimum valid ship capacity
24        return leftBoundary;
25    }
26
27    // Helper method to determine if the given capacity can ship all weights within the given days
28    private boolean canShip(int[] weights, int capacity, int days) {
29        int currentLoad = 0;   // Current weight load of the ship
30        int dayCount = 1;      // Start with the first day
31
32        // Iterating over each weight to simulate the shipping process
33        for (int weight : weights) {
34            currentLoad += weight;
35            // If adding weight exceeds capacity, ship current load and increment day counter
36            if (currentLoad > capacity) {
37                currentLoad = weight; // Reset load with the current weight
38                dayCount++;           // Move to the next day
39            }
40        }
41      
42        // If the number of shipping days needed is within the allowed range, return true
43        return dayCount <= days;
44    }
45}
46
1#include <vector>
2#include <algorithm> // For max()
3using std::vector;
4using std::max;
5
6class Solution {
7public:
8    // Function to find the minimum capacity of a ship that can ship all the packages within 'days' days
9    int shipWithinDays(vector<int>& weights, int days) {
10        int minCapacity = 0; // Lower boundary of binary search - max weight in the shipment
11        int maxCapacity = 0; // Upper boundary of binary search - sum of all weights
12      
13        // Calculate the minimum and maximum capacity
14        for (int weight : weights) {
15            minCapacity = max(minCapacity, weight);
16            maxCapacity += weight;
17        }
18      
19        // Lambda function to check if mid value can work as the capacity
20        auto canShipWithCapacity = [&](int capacity) -> bool {
21            int currentWeightSum = 0; // Current weight sum of the ongoing shipment
22            int dayCount = 1; // Counter for the number of days needed
23
24            for (int weight : weights) {
25                currentWeightSum += weight;
26              
27                // Check if adding the current weight exceeds capacity, if so, reset for the next day
28                if (currentWeightSum > capacity) {
29                    currentWeightSum = weight;
30                    dayCount++;
31                }
32            }
33
34            // Check if we can ship within the given number of days with the current capacity
35            return dayCount <= days;
36        };
37      
38        // Binary search to find the minimum capacity required
39        while (minCapacity < maxCapacity) {
40            int midCapacity = (minCapacity + maxCapacity) / 2;
41          
42            // Check if the midCapacity can be a possible solution, adjust search boundaries based on it
43            if (canShipWithCapacity(midCapacity)) {
44                maxCapacity = midCapacity;
45            } else {
46                minCapacity = midCapacity + 1;
47            }
48        }
49      
50        // Return the minimum capacity needed to ship within 'days' days
51        return minCapacity;
52    }
53};
54
1function shipWithinDays(weights: number[], days: number): number {
2    // Initialize the lower and upper bounds for the binary search
3    let lowerBound = 0;
4    let upperBound = 0;
5
6    // Calculate the initial bounds for the capacity of the ship
7    for (const weight of weights) {
8        lowerBound = Math.max(lowerBound, weight); // The ship's capacity must be at least as much as the heaviest package
9        upperBound += weight; // The maximum capacity is the sum of all weights, i.e., shipping all at once
10    }
11
12    // Function to determine if it's possible to ship all packages within 'days' given a maximum capacity 'maxCapacity'
13    const canShipInDays = (maxCapacity: number): boolean => {
14        let currentWeightSum = 0; // Current total weight in the current shipment
15        let requiredDays = 1;     // Start with 1 day, the minimum possible
16
17        for (const weight of weights) {
18            currentWeightSum += weight;
19
20            // If adding the current weight exceeds max capacity, need a new shipment (next day)
21            if (currentWeightSum > maxCapacity) {
22                currentWeightSum = weight; // Reset the currentWeightSum with the current weight as the start for the next day
23                ++requiredDays;           // Increment the day counter as we move to the next day
24            }
25        }
26
27        // Return true if the number of required days is less than or equal to the given days, false otherwise
28        return requiredDays <= days;
29    };
30
31    // Perform a binary search to find the minimum capacity needed to ship within 'days'
32    while (lowerBound < upperBound) {
33        const midCapacity = Math.floor((lowerBound + upperBound) / 2); // Mid-point of the current bounds
34
35        // If it's possible to ship with this capacity, reduce the upper bound to midCapacity
36        if (canShipInDays(midCapacity)) {
37            upperBound = midCapacity;
38        } else {
39            // Otherwise, increase the lower bound just above midCapacity
40            lowerBound = midCapacity + 1;
41        }
42    }
43
44    // The lower bound at the end of the binary search will be the minimum capacity needed to meet the requirement
45    return lowerBound;
46}
47
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Time and Space Complexity

The time complexity of the code is O(n * log(S)), where n is the number of elements in weights, and S is the sum of weights minus the maximum weight in weights. This is because the binary search is performed over a range with left and right as lower and upper bounds, respectively. The check function, called at each step of the binary search, runs in O(n) time since it iterates through all the elements of weights. Since the binary search narrows the range by half each time, it will run log(S - max(weights)) times.

The space complexity of the code is O(1) as it uses a constant amount of space. The check function uses variables to store the current weight sum and the count of days, both of which do not depend on the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫