Capacity To Ship Packages Within D Days

Medium

Flipkart

2 views

Topics:

ArraysBinary Search

A conveyor belt has packages that must be shipped from one port to another within days days.

The 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.

Return 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:

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 the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Constraints:

1 <= days <= weights.length <= 5 * 10⁴
1 <= weights[i] <= 500

Try coding it in LeetCode

Capacity To Ship Packages Within D Days

Medium

Flipkart

2 views

Topics:

ArraysBinary Search

A conveyor belt has packages that must be shipped from one port to another within days days.

The 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.

Return 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:

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 the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Constraints:

1 <= days <= weights.length <= 5 * 10⁴
1 <= weights[i] <= 500

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the `weights` array size and the individual weight values? Could any weight be zero or negative?
What are the constraints on the number of `days`? Can `days` be zero or negative, or larger than the number of packages?
If it's impossible to ship all packages within the given `days`, what value should I return?
Are the weights integers? Should I expect any floating-point values?
Is there a maximum or minimum constraint on the total weight of all packages combined?

Brute Force Solution

Approach

The brute force way to solve this problem is to try every possible weight capacity for the shipping truck. We want to find the smallest capacity that still allows us to ship all packages within the given number of days.

Here's how the algorithm would work step-by-step:

Start with a very small capacity for the shipping truck - even smaller than the weight of the heaviest package.
See if it's possible to ship all the packages within the allowed number of days, given that capacity. If it's not possible, increase the capacity a little bit.
Keep increasing the capacity, one small step at a time. Each time you increase it, check if you can ship all packages within the allowed time.
When checking if you can ship all packages, just load the packages onto the truck one by one until it's full. Then, send the truck and start loading for the next day.
Repeat this process of loading and shipping each day.
If, with a certain capacity, you run out of days before you ship all the packages, then that capacity is too small, and you need to increase it.
The first capacity that allows you to ship all packages within the allowed number of days is the answer we are looking for.

Code Implementation

def capacity_to_ship_packages(weights, days):
    smallest_possible_capacity = 1
    while True:
        # Keep testing increasingly larger capacities until we find one that works
        if can_ship_all_packages(weights, days, smallest_possible_capacity):
            return smallest_possible_capacity
        smallest_possible_capacity += 1

def can_ship_all_packages(weights, days, current_capacity):
    number_of_days_needed = 1
    current_weight_on_truck = 0

    for weight in weights:
        # If adding the next package exceeds the current capacity, move to the next day
        if current_weight_on_truck + weight > current_capacity:

            number_of_days_needed += 1
            current_weight_on_truck = 0

        current_weight_on_truck += weight

        # If we exceeded the total number of days allowed, this capacity is too small
        if number_of_days_needed > days:

            return False

    return True

Big(O) Analysis

Time Complexity

O(S * n) – Let n be the number of packages (length of the weights array). The brute force approach iterates through possible capacities, starting from a small value and incrementing until a valid capacity is found. Let S be the total search space for the capacity; in the worst case, we would check every possible capacity value until we find one that works. For each capacity value, we iterate through the array of weights to simulate the shipping process, taking O(n) time. Therefore, the overall time complexity is O(S * n), where S is the number of different capacity values we try.

Space Complexity

O(1) – The described brute force approach primarily uses a few variables to track the current capacity, the number of days used, and the current weight being loaded onto the truck. No auxiliary data structures like arrays, hash maps, or significant recursion are utilized. Therefore, the space used remains constant irrespective of the number of packages (N), resulting in O(1) space complexity.

Optimal Solution

Approach

The trick is to efficiently find the smallest possible carrying capacity that still allows us to ship all packages within the given number of days. We use a method that avoids checking every capacity by narrowing down the possibilities, eventually pinpointing the optimal one.

Here's how the algorithm would work step-by-step:

First, figure out the smallest possible capacity a single ship can have: it has to be able to carry the single heaviest package.
Next, calculate the largest possible capacity. This would be the sum of all the packages' weights.
Now, think of capacity as a range of possibilities between the smallest and largest. Pick the middle of this range as a 'test' capacity.
Using this test capacity, simulate shipping all the packages. Count how many days it takes to ship everything.
If it takes too many days with this test capacity, it means the capacity is too small. Adjust the range by setting the smallest possible capacity to be just above this failed test capacity.
If it takes fewer days (or the exact number of days), it means the capacity might be too big, but it's a candidate. So, adjust the range by setting the largest possible capacity to this test capacity. This will allow us to look for a possibly smaller capacity that works.
Repeat the process of picking the middle of the new range, simulating shipping, and adjusting the range until the smallest and largest possible capacities are the same. That final value is the smallest capacity that allows us to ship within the given number of days.

Code Implementation

def capacity_to_ship_packages_within_d_days(weights, days):
    minimum_capacity = max(weights)
    maximum_capacity = sum(weights)

    while minimum_capacity < maximum_capacity:
        mid_capacity = (minimum_capacity + maximum_capacity) // 2
        days_needed = 1
        current_load = 0

        for weight in weights:
            if current_load + weight > mid_capacity:
                # Need a new day, so increment the day count.
                days_needed += 1
                current_load = 0

            current_load += weight

        # If we need more days, the capacity is too small.
        if days_needed > days:
            minimum_capacity = mid_capacity + 1

        else:
            # This capacity works, try to find a smaller one.
            maximum_capacity = mid_capacity

    return minimum_capacity

Big(O) Analysis

Time Complexity

O(n * log(sum of weights - max weight)) – The algorithm employs a binary search approach to find the optimal capacity. The search space is defined by the range between the maximum weight of a single package and the sum of all package weights. The binary search iteratively narrows this range, taking logarithmic time relative to the size of the range, which can be expressed as log(sum of weights - max weight). Within each iteration of the binary search, we simulate shipping the packages to determine the number of days required, which takes linear time, O(n), where n is the number of packages. Therefore, the overall time complexity is O(n * log(sum of weights - max weight)).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store the smallest capacity, largest capacity, test capacity, and the number of days taken for shipping. These variables occupy constant space regardless of the number of packages (N). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty weights array	Return 0 or throw an IllegalArgumentException as there's nothing to ship, preventing a NullPointerException or incorrect calculation.
Days is less than or equal to 0	Throw an IllegalArgumentException since it is impossible to ship packages within a non-positive number of days.
Days is greater than or equal to the number of packages (weights.length)	The minimum capacity is the maximum weight of a single package in the weights array because each package can be shipped on its own day.
All weights are the same and 'days' is 1	The capacity should be the sum of all weights, ensuring correct capacity when all items are shipped together.
Weights array contains a single very large weight	The minimum capacity will be the large weight, since it must be shipped regardless of the value of 'days'.
Sum of all weights is very large, potentially causing integer overflow when calculating the maximum possible capacity	Use long data type for intermediate calculations like sum to prevent integer overflow, which ensures that very large weights do not lead to incorrect capacities.
Binary Search: Initial 'left' pointer is calculated incorrectly	The 'left' pointer (minimum capacity) should be the maximum single weight, which guarantees it is no less than any weight
Binary Search: 'right' pointer (maximum capacity) is calculated incorrectly	The 'right' pointer (maximum capacity) should be the sum of all weights, ensuring all weights can be carried in one day.