Find Minimum Ship Capacity to Ship Packages in D Days Binary Search Approach

Problem Statement❯

You are given an array of package weights and a number D representing the number of days within which all the packages must be delivered. Each day, you can ship packages in the given order, but the total weight of the packages shipped on a day cannot exceed a certain ship capacity.

Your task is to determine the minimum weight capacity of the ship so that all packages can be shipped within D days.

Note: Packages must be shipped in order and cannot be split.

Examples❯

Weights	Days (D)	Minimum Capacity	Description
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]	5	15	One possible allocation: [1,2,3,4,5], [6], [7], [8], [9,10]
[3, 2, 2, 4, 1, 4]	3	6	Minimum capacity needed to fit the packages in 3 days
[10, 50, 50, 10]	2	100	First day: [10, 50]; second day: [50, 10]
[5, 5, 5, 5]	4	5	Each package on a separate day, minimum possible capacity is 5
[5, 5, 5, 5]	1	20	All packages on the same day, total weight = 20
[7, 2, 5, 10, 8]	2	18	Day 1: [7,2,5], Day 2: [10,8]
[1]	1	1	Only one package, one day
[]	1	0	No packages to ship, capacity needed is 0
[4, 8, 5]	5	8	More days than packages, so capacity can be equal to the largest weight

Visualization Player

Solution❯

Understanding the Problem

We are given an array of package weights and a number D representing the number of days within which all packages must be shipped. The task is to find the minimum ship capacity that allows us to ship all the packages in order, within D days. Each day, the ship can carry a contiguous group of packages without exceeding its maximum weight capacity. Packages cannot be split and must be shipped in the given order.

Step-by-Step Solution with Example

Step 1: Understand the Role of Capacity

Capacity means the maximum total weight the ship can carry in a single day. For instance, if the capacity is 10, then the ship can carry packages like [3,7], but not [6,5] since 6+5 = 11 exceeds the limit.

Step 2: Binary Search Strategy

We aim to find the smallest valid capacity. To do this efficiently, we use binary search between two limits:

Lower bound: the maximum weight of any single package (since the ship must at least carry that).
Upper bound: the total weight of all packages (meaning all shipped in one day).

Step 3: Check If a Given Capacity Works

For any candidate capacity in our binary search, we simulate the shipping process:

Start on day 1 with current day load = 0.
Iterate through the packages:

Add the current package to the current day's load.
If this exceeds the capacity, increment the day count and start a new day with the current package.

If the number of days used exceeds D, the capacity is too small. Otherwise, it's a valid capacity and we try smaller values to minimize it.

Step 4: Example

Input:
weights = [1,2,3,4,5,6,7,8,9,10], D = 5

Step-by-step:
- The max weight is 10 → minimum possible capacity.
- Total weight is 55 → maximum possible capacity.
- We perform binary search between 10 and 55.

First mid = 32:
- Simulated days needed: 3 (valid, try smaller capacity)
Next mid = 21:
- Simulated days needed: 4 (valid, try smaller)
Next mid = 15:
- Simulated days needed: 5 (valid, try smaller)
Next mid = 12:
- Simulated days needed: 6 (too many, try larger)
Next mid = 13:
- Simulated days needed: 5 (valid, try smaller)
...
Eventually, we find that the minimum capacity that allows shipping in 5 days is 15.

Edge Cases

Only one package: If there's one package and one day, the capacity must be equal to the package weight.
More days than packages: We can ship one package per day, so capacity only needs to handle the largest package.
Empty package list: No packages to ship. Return 0 or handle as a special case depending on constraints.
Very large weights or days: Use 64-bit integers to avoid overflow when summing weights or calculating mid values in binary search.

Finally

This problem is a classic example of using binary search on the answer space. Instead of iterating through all possible capacities, we strategically test midpoints to narrow the range. By simulating the shipping process for each tested capacity, we ensure the chosen value truly satisfies the D-day constraint. The logic can be extended to similar scheduling and load-balancing problems as well.

Algorithm Steps❯

Set the search range: low = max(weights) and high = sum(weights).
While low ≤ high:
→ Compute mid = (low + high) / 2.
→ Check if it’s possible to ship all packages within D days using mid as the capacity.
→ If possible, store mid as answer and try to minimize (high = mid - 1).
→ Otherwise, increase capacity (low = mid + 1).
Return the minimum valid capacity found.

Code

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>

int canShip(int weights[], int n, int D, int capacity) {
    int days = 1, total = 0;
    for (int i = 0; i < n; i++) {
        if (total + weights[i] > capacity) {
            days++;
            total = 0;
        }
        total += weights[i];
    }
    return days <= D;
}

int shipWithinDays(int weights[], int n, int D) {
    int low = weights[0], high = 0;
    for (int i = 0; i < n; i++) {
        if (weights[i] > low) low = weights[i];
        high += weights[i];
    }
    int result = high;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (canShip(weights, n, D, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int weights[] = {1,2,3,4,5,6,7,8,9,10};
    int n = sizeof(weights) / sizeof(weights[0]);
    int D = 5;
    printf("Minimum capacity: %d\n", shipWithinDays(weights, n, D));
    return 0;
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n)	When the optimal capacity is found early in the binary search range and only a single pass over weights is needed to validate.
Average Case	O(n * log(sum - max))	Binary search runs over the capacity range and for each capacity, we do a full scan of weights.
Worst Case	O(n * log(sum - max))	In the worst case, binary search tries nearly all capacity values between max(weights) and sum(weights).

Space Complexity❯

O(1)

Explanation: No extra space is used except a few variables for computation.

⬅ Previous TopicFind the Smallest Divisor Given a Threshold

Next Topic ⮕Kth Missing Positive Number

Comments

Loading comments...