Minimum Space Wasted From Packaging - Practice Coding Problems

Minimum Space Wasted From Packaging - Problem

You have n packages that you are trying to place in boxes, one package in each box. There are m suppliers that each produce boxes of different sizes (with infinite supply). A package can be placed in a box if the size of the package is less than or equal to the size of the box.

The package sizes are given as an integer array packages, where packages[i] is the size of the i-th package. The suppliers are given as a 2D integer array boxes, where boxes[j] is an array of box sizes that the j-th supplier produces.

You want to choose a single supplier and use boxes from them such that the total wasted space is minimized. For each package in a box, we define the space wasted to be size of the box - size of the package. The total wasted space is the sum of the space wasted in all the boxes.

For example: if you have to fit packages with sizes [2,3,5] and the supplier offers boxes of sizes [4,8], you can fit the packages of size-2 and size-3 into two boxes of size-4 and the package with size-5 into a box of size-8. This would result in a waste of (4-2) + (4-3) + (8-5) = 6.

Return the minimum total wasted space by choosing the box supplier optimally, or -1 if it is impossible to fit all the packages inside boxes. Since the answer may be large, return it modulo 10^9 + 7.

Input & Output

Example 1 — Basic Case

$ Input: packages = [2,3,5], boxes = [[4,8],[2,3,4],[1,4]]

› Output: 6

💡 Note: Best supplier is [4,8]: package 2→box 4 (waste 2), package 3→box 4 (waste 1), package 5→box 8 (waste 3). Total waste = 6.

Example 2 — Impossible Case

$ Input: packages = [2,3,5], boxes = [[1,4],[2,3]]

› Output: -1

💡 Note: No supplier can fit package 5. First supplier's largest box is 4, second supplier's largest is 3, both < 5.

Example 3 — Perfect Fit

$ Input: packages = [3,5], boxes = [[3,5]]

› Output: 0

💡 Note: Perfect match: package 3→box 3 (waste 0), package 5→box 5 (waste 0). Total waste = 0.

Constraints

1 ≤ packages.length ≤ 10⁵
1 ≤ boxes.length ≤ 10⁵
1 ≤ boxes[j].length ≤ 10⁵
1 ≤ packages[i], boxes[j][k] ≤ 10⁹
Sum of boxes[j].length ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Packages [2,3,5] and suppliers [[4,8], [2,3,4], [1,4]]

Process

For each supplier, find smallest box ≥ package size

Output

Return minimum total waste across all suppliers

Key Takeaway

🎯 Key Insight: Sort both packages and boxes, then use binary search to efficiently find the smallest suitable box for each package

Asked in

a Amazon 45 G Google 32 M Microsoft 28

The key insight is to sort packages and boxes, then use binary search to efficiently find the smallest suitable box for each package. The optimal approach combines sorting + binary search to achieve O(n log n + m×k log k + m×n log k) time complexity. For each supplier, we find the minimum waste by matching each package to its smallest fitting box.

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum + Binary Search	O(n log n + m × k log k + m × n log k)	O(k)	Use prefix sums to optimize waste calculation after binary search
Brute Force	O(m × n × k)	O(1)	For each supplier, try all possible box assignments and calculate total waste
Binary Search Optimization	O(n log n + m × k log k + m × n log k)	O(1)	Sort boxes and use binary search to find the smallest suitable box for each package

Prefix Sum + Binary Search — Algorithm Steps

Sort packages and each supplier's boxes
For each supplier, calculate prefix sums of box sizes
Use binary search and prefix sums to efficiently compute total waste

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Sort packages and boxes, build prefix sum arrays

Binary search for suitable boxes

Optimize

Use prefix sums for efficient waste calculation

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int binarySearch(int* arr, int size, int target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = (left + right) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int solution(int* packages, int packagesSize, int** boxes, int* boxesSizes, int boxesSize) {
    const int MOD = 1e9 + 7;
    qsort(packages, packagesSize, sizeof(int), compare);
    long long minWaste = LLONG_MAX;
    
    for (int s = 0; s < boxesSize; s++) {
        qsort(boxes[s], boxesSizes[s], sizeof(int), compare);
        int nBoxes = boxesSizes[s];
        
        // Build prefix sum array
        long long* prefix = malloc((nBoxes + 1) * sizeof(long long));
        prefix[0] = 0;
        for (int i = 0; i < nBoxes; i++) {
            prefix[i + 1] = prefix[i] + boxes[s][i];
        }
        
        long long totalWaste = 0;
        int possible = 1;
        
        for (int p = 0; p < packagesSize; p++) {
            int idx = binarySearch(boxes[s], nBoxes, packages[p]);
            if (idx == nBoxes) {
                possible = 0;
                break;
            }
            totalWaste += boxes[s][idx] - packages[p];
        }
        
        if (possible && totalWaste < minWaste) {
            minWaste = totalWaste;
        }
        
        free(prefix);
    }
    
    return minWaste == LLONG_MAX ? -1 : (int)(minWaste % MOD);
}

int main() {
    int packages[] = {2, 3, 5};
    int packagesSize = 3;
    
    int box1[] = {4, 8};
    int box2[] = {1, 4, 9};
    int* boxes[] = {box1, box2};
    int boxesSizes[] = {2, 3};
    int boxesSize = 2;
    
    printf("%d\n", solution(packages, packagesSize, boxes, boxesSizes, boxesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m × k log k + m × n log k)

Same search complexity but faster waste calculation using prefix sums

⚡ Linearithmic

Space Complexity

O(k)

Extra space for prefix sum arrays for each supplier

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 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

Prefix Sum + Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler