Minimum Shipping Capacity

Problem

You’re a logistics manager preparing to ship products from a warehouse. Each product type has both a quantity and a weight per item. Shipping boxes have TWO constraints:

Rules:

Each product type must be packed separately
All boxes have the same capacity and weight limits
A box can hold at most capacity items OR maxWeightPerBox kg, whichever comes first
Items must be whole numbers (can’t pack fractional items)

Given arrays of quantities and weights per item, plus box and weight constraints, find the minimum box capacity needed to ship all products.

Example 1

Input:

quantities = [8, 12, 5]
weights = [2, 3, 1]  # kg per item
maxBoxes = 6
maxWeightPerBox = 20  # kg

Output: 5

Explanation: With capacity 5:

Product 0 (8 items @ 2kg): min(5, 10, 8) = 5 items/box → needs 2 boxes (5 + 3 items)
Product 1 (12 items @ 3kg): min(5, 6, 12) = 5 items/box → needs 3 boxes (5 + 5 + 2 items)
Product 2 (5 items @ 1kg): min(5, 20, 5) = 5 items/box → needs 1 box Total: 6 boxes ≤ 6 ✓

Example 2

Input:

quantities = [10, 15, 8]
weights = [5, 2, 3]
maxBoxes = 10
maxWeightPerBox = 15

Output: 4

Explanation: With capacity 4:

Product 0 (10 items @ 5kg): min(4, ⌊15/5⌋, remaining) = 3 items/box → needs 4 boxes
Product 1 (15 items @ 2kg): min(4, ⌊15/2⌋, remaining) = 4 items/box → needs 4 boxes
Product 2 (8 items @ 3kg): min(4, ⌊15/3⌋, remaining) = 4 items/box → needs 2 boxes Total: 10 boxes ≤ 10 ✓

Building Intuition

You’re shipping products from a warehouse, but here’s the twist: each product has both a quantity and a weight per item. Your shipping boxes have two constraints:

Capacity limit: Maximum number of items per box
Weight limit: 20kg per box

Whichever limit is hit first determines how many items fit in that box.

Given: quantities = [8, 12, 5], weights = [2, 3, 1] kg per item, maxBoxes = 6, maxWeightPerBox = 20

With capacity = 5 items/box:

Product 0 (8 items @ 2kg each): Each box can hold min(5, ⌊20/2⌋, remaining) = min(5, 10, remaining) = 5 items. Needs 2 boxes: [5 items/10kg] + [3 items/6kg]
Product 1 (12 items @ 3kg each): Each box can hold min(5, ⌊20/3⌋, remaining) = min(5, 6, remaining) = 5 items. Needs 3 boxes: [5 items/15kg] + [5 items/15kg] + [2 items/6kg]
Product 2 (5 items @ 1kg each): Each box can hold min(5, ⌊20/1⌋, remaining) = min(5, 20, 5) = 5 items. Needs 1 box: [5 items/5kg]

Total: 2 + 3 + 1 = 6 boxes, which exactly meets our limit of 6 ✓

Can we find a smaller capacity that still works?

Brute Force: Try Every Capacity?

The brute force approach would be to try every possible capacity from 1 up to max(quantities) and check each one:

bruteForce(quantities, weights, maxBoxes, maxWeightPerBox)
    for capacity = 1 to max(quantities)
        boxes = countBoxesNeeded(capacity)
        if boxes <= maxBoxes
            return capacity
    return max(quantities)

The counting function now needs to handle weight constraints:

This works, but if the largest quantity is 1,000,000, we’d need up to 1 million iterations. Can we do better?

The Monotonic Property

If capacity c works (uses ≤ maxBoxes), then any capacity larger than c also works. Bigger boxes = fewer boxes needed.

This holds even with weight constraints. If we can fit items with capacity 5, we can definitely fit them with capacity 6 (assuming weight doesn’t become the limiting factor, which it won’t because we’re still packing the same items).

This monotonic property tells us the search space is divided into two regions: capacities that don’t work (too small) and capacities that do work (large enough). We want to find the boundary i.e. the smallest capacity that works.

Binary search is perfect for finding boundaries in monotonic search spaces.

When the answer lies in a range and there’s a monotonic property (if X works, all values greater/less than X also work), binary search can find the optimal answer in O(log n) iterations instead of O(n).

How Binary Search Works Here

For each candidate capacity mid, we check if it’s feasible by counting how many boxes we’d need. This is where the weight constraint makes things interesting:

For each product, we pack items into boxes until we’ve packed everything. Each box can hold:

At most capacity items (the capacity limit we’re testing)
At most floor(maxWeightPerBox / weights[i]) items (the weight limit)
At most remaining items (can’t pack more than we have)

We take the minimum of these three values.

def minimumShippingCapacity(quantities, weights, maxBoxes, maxWeightPerBox):
    def countBoxes(capacity):
        boxes = 0
        for i in range(len(quantities)):
            remaining = quantities[i]
            while remaining > 0:
                itemsThisBox = min(capacity, maxWeightPerBox // weights[i], remaining)
                boxes += 1
                remaining -= itemsThisBox
        return boxes
    
    left = 1
    right = max(quantities)
    
    while left < right:
        mid = (left + right) // 2
        if countBoxes(mid) <= maxBoxes:
            right = mid
        else:
            left = mid + 1
    
    return left

class Solution {
    public int minimumShippingCapacity(int[] quantities, int[] weights, int maxBoxes, int maxWeightPerBox) {
        int left = 1;
        int right = 0;
        for (int q : quantities) {
            right = Math.max(right, q);
        }
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (countBoxes(quantities, weights, mid, maxWeightPerBox) <= maxBoxes) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private int countBoxes(int[] quantities, int[] weights, int capacity, int maxWeightPerBox) {
        int boxes = 0;
        for (int i = 0; i < quantities.length; i++) {
            int remaining = quantities[i];
            while (remaining > 0) {
                int itemsThisBox = Math.min(Math.min(capacity, maxWeightPerBox / weights[i]), remaining);
                boxes++;
                remaining -= itemsThisBox;
            }
        }
        return boxes;
    }
}

func minimumShippingCapacity(quantities []int, weights []int, maxBoxes int, maxWeightPerBox int) int {
    countBoxes := func(capacity int) int {
        boxes := 0
        for i := range quantities {
            remaining := quantities[i]
            for remaining > 0 {
                itemsThisBox := capacity
                if maxWeightPerBox / weights[i] < itemsThisBox {
                    itemsThisBox = maxWeightPerBox / weights[i]
                }
                if remaining < itemsThisBox {
                    itemsThisBox = remaining
                }
                boxes++
                remaining -= itemsThisBox
            }
        }
        return boxes
    }
    
    left := 1
    right := 0
    for _, q := range quantities {
        if q > right {
            right = q
        }
    }
    
    for left < right {
        mid := left + (right - left) / 2
        if countBoxes(mid) <= maxBoxes {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left
}

function minimumShippingCapacity(quantities: number[], weights: number[], maxBoxes: number, maxWeightPerBox: number): number {
    function countBoxes(capacity: number): number {
        let boxes = 0;
        for (let i = 0; i < quantities.length; i++) {
            let remaining = quantities[i];
            while (remaining > 0) {
                const itemsThisBox = Math.min(
                    capacity,
                    Math.floor(maxWeightPerBox / weights[i]),
                    remaining
                );
                boxes++;
                remaining -= itemsThisBox;
            }
        }
        return boxes;
    }
    
    let left = 1;
    let right = Math.max(...quantities);
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (countBoxes(mid) <= maxBoxes) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

Walkthrough

Let’s trace through quantities = [8, 12, 5], weights = [2, 3, 1] with maxBoxes = 6 and maxWeightPerBox = 20 step by step.

Step 1: Initialize the search bounds

We establish the range of possible capacities. The minimum is 1 (smallest possible box). The maximum is max(quantities) = 12 because a box that holds 12 items can ship any single product type in one box (assuming weight allows).

Our search space is [1, 12]. Now we start binary searching for the minimum valid capacity.

Step 2: First binary search iteration

We calculate mid = (1 + 12) / 2 = 6. Can we ship everything with capacity 6 using at most 6 boxes?

Let’s count:

Product 0 (8 items @ 2kg): min(6, floor(20/2), 8) = min(6, 10, 8) = 6 items/box → needs ceil(8/6) = 2 boxes
Product 1 (12 items @ 3kg): min(6, floor(20/3), 12) = min(6, 6, 12) = 6 items/box → needs ceil(12/6) = 2 boxes
Product 2 (5 items @ 1kg): min(6, floor(20/1), 5) = min(6, 20, 5) = 5 items/box → needs 1 box

Total: 2 + 2 + 1 = 5 boxes ≤ 6 ✓

Since 5 ≤ 6, capacity 6 works! But maybe we can do better with smaller boxes. We set right = mid = 6 to search the lower half.

Step 3: Second binary search iteration

Now left = 1, right = 6. We try mid = (1 + 6) / 2 = 3.

Let’s count:

Product 0 (8 items @ 2kg): min(3, floor(20/2), 8) = min(3, 10, 8) = 3 items/box → needs ceil(8/3) = 3 boxes
Product 1 (12 items @ 3kg): min(3, floor(20/3), 12) = min(3, 6, 12) = 3 items/box → needs ceil(12/3) = 4 boxes
Product 2 (5 items @ 1kg): min(3, floor(20/1), 5) = min(3, 20, 5) = 3 items/box → needs ceil(5/3) = 2 boxes

Total: 3 + 4 + 2 = 9 boxes > 6 ✗

Capacity 3 is too small! We set left = mid + 1 = 4.

Step 4: Third binary search iteration

Now left = 4, right = 6. We try mid = (4 + 6) / 2 = 5.

Let’s count:

Product 0 (8 items @ 2kg): min(5, floor(20/2), 8) = min(5, 10, 8) = 5 items/box → needs ceil(8/5) = 2 boxes
Product 1 (12 items @ 3kg): min(5, floor(20/3), 12) = min(5, 6, 12) = 5 items/box → needs ceil(12/5) = 3 boxes
Product 2 (5 items @ 1kg): min(5, floor(20/1), 5) = min(5, 20, 5) = 5 items/box → needs 1 box

Total: 2 + 3 + 1 = 6 boxes ≤ 6 ✓

Capacity 5 works! Try smaller: right = mid = 5.

Step 5: Fourth binary search iteration

Now left = 4, right = 5. We try mid = (4 + 5) / 2 = 4.

Let’s count:

Product 0 (8 items @ 2kg): min(4, floor(20/2), 8) = min(4, 10, 8) = 4 items/box → needs ceil(8/4) = 2 boxes
Product 1 (12 items @ 3kg): min(4, floor(20/3), 12) = min(4, 6, 12) = 4 items/box → needs ceil(12/4) = 3 boxes
Product 2 (5 items @ 1kg): min(4, floor(20/1), 5) = min(4, 20, 5) = 4 items/box → needs ceil(5/4) = 2 boxes

Total: 2 + 3 + 2 = 7 boxes > 6 ✗

Capacity 4 is too small! We set left = mid + 1 = 5.

Step 6: Converged

Now left = right = 5. The loop ends, and we return 5.

Result: 5

The minimum box capacity is 5 items per box. With this capacity and weight constraints:

Product 0 (8 items @ 2kg each): 2 boxes [5 items/10kg] + [3 items/6kg]
Product 1 (12 items @ 3kg each): 3 boxes [5 items/15kg] × 2 + [2 items/6kg]
Product 2 (5 items @ 1kg each): 1 box [5 items/5kg]

Total: 2 + 3 + 1 = 6 boxes, which exactly meets our limit of 6.

Solution

Recognizing This Pattern

This problem follows the “binary search on answer” pattern with an added twist: compound constraints. Look for these signals:

Find minimum/maximum that satisfies multiple constraints - here, minimum capacity with both box limit and weight limit
Monotonic relationship despite compound constraints - if capacity X works, X+1 also works (since we’re packing the same items)
Bounded search space - capacity ranges from 1 to max(quantities)
Complex feasibility check - counting boxes requires simulating packing with multiple constraints

The difference from simpler binary search problems is the counting function is more complex because each box must satisfy two independent constraints (capacity AND weight). You can’t use simple ceiling division - you must simulate the packing process.