Capacity To Ship Packages Within D Days - Practice Coding Problems

Capacity To Ship Packages Within D Days - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: weights = [1,2,3,1,1], days = 4

› Output: 6

💡 Note: Ship capacity 6: Day 1 [1,2,3] (6 units), Day 2 [1] (1 unit), Day 3 [1] (1 unit). Total 3 days ≤ 4.

Example 2 — Tight Constraint

$ Input: weights = [3,2,2,4,1,4], days = 3

› Output: 6

💡 Note: Ship capacity 6: Day 1 [3,2] (5 units), Day 2 [2,4] (6 units), Day 3 [1,4] (5 units). Exactly 3 days.

Example 3 — Single Heavy Package

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

› Output: 15

💡 Note: Ship capacity 15 allows balanced distribution across 5 days to handle all packages efficiently.

Constraints

1 ≤ days ≤ weights.length ≤ 5 × 10⁴
1 ≤ weights[i] ≤ 500

Visualization

Tap to expand

Understanding the Visualization

Input

Packages with weights [1,2,3,1,1] and 4-day deadline

Process

Binary search between min (3) and max (8) capacity

Output

Minimum capacity 6 that ships all packages in ≤4 days

Key Takeaway

🎯 Key Insight: Binary search on answer space works because if capacity X can ship within days, then X+1 can too (monotonic property).

Asked in

a Amazon 45 G Google 35 f Facebook 25 M Microsoft 20

The key insight is recognizing this as a binary search problem on the answer space. The optimal approach uses binary search to find the minimum ship capacity, achieving O(n × log(sum)) time complexity compared to O(n × sum) brute force.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer Space	O(n × log(sum))	O(1)	Use binary search to find minimum capacity that works within given days
Brute Force Linear Search	O(n × (sum - max))	O(1)	Try every possible capacity from max weight to sum of all weights

Binary Search on Answer Space — Algorithm Steps

Step 1: Set search range from max(weights) to sum(weights)
Step 2: Binary search - for each mid capacity, check if it can ship within days
Step 3: If capacity works, search left half; otherwise search right half

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Range

Set left=max(weights), right=sum(weights)

Binary Search

Test middle capacity, narrow search space based on result

Converge

Continue until left==right, that's the minimum capacity

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canShip(int* weights, int weightsSize, int capacity, int days) {
    int currentWeight = 0;
    int daysNeeded = 1;
    
    for (int i = 0; i < weightsSize; i++) {
        if (currentWeight + weights[i] > capacity) {
            daysNeeded++;
            currentWeight = weights[i];
        } else {
            currentWeight += weights[i];
        }
    }
    
    return daysNeeded <= days;
}

int solution(int* weights, int weightsSize, int days) {
    int left = weights[0];
    int right = 0;
    
    for (int i = 0; i < weightsSize; i++) {
        if (weights[i] > left) {
            left = weights[i];
        }
        right += weights[i];
    }
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canShip(weights, weightsSize, mid, days)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int weights[1000];
    int weightsSize = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            weights[weightsSize++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int days;
    scanf("%d", &days);
    
    int result = solution(weights, weightsSize, days);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(sum))

Binary search takes O(log(sum)) iterations, each iteration simulates shipping in O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only uses constant extra variables for binary search bounds

✓ Linear Space

89.7K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer Space — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler