# Minimum Space Wasted From Packaging
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-space-wasted-from-packaging)
Canonical: https://scaleengineer.com/dsa/problems/minimum-space-wasted-from-packaging
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Two Sigma](https://scaleengineer.com/companies/two-sigma)
---
## 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 `ith` package. The suppliers are given as a 2D integer array `boxes`, where `boxes[j]` is an array of **box sizes** that the `jth` 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** `109 + 7`.

**Example 1:**

**Input:** packages = [2,3,5], boxes = [[4,8],[2,8]]
**Output:** 6
**Explanation**: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.
The total waste is (4-2) + (4-3) + (8-5) = 6.

**Example 2:**

**Input:** packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
**Output:** -1
**Explanation:** There is no box that the package of size 5 can fit in.

**Example 3:**

**Input:** packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
**Output:** 9
**Explanation:** It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.
The total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.

**Constraints:**

* `n == packages.length`
* `m == boxes.length`
* `1 <= n <= 105`
* `1 <= m <= 105`
* `1 <= packages[i] <= 105`
* `1 <= boxes[j].length <= 105`
* `1 <= boxes[j][k] <= 105`
* `sum(boxes[j].length) <= 105`
* The elements in `boxes[j]` are **distinct**.

# Approaches
## Iterating Packages for Each Supplier
A relatively straightforward approach is to consider each supplier one by one. For a given supplier, we need to calculate the total wasted space if we use their boxes. To minimize waste for a single package, we must choose the smallest box from the supplier that is large enough to hold the package.
**Time:** O(N log N + sum(k_j log k_j + N log k_j)) for j from 0 to M-1. Here, N is the number of packages, M is the number of suppliers, and k_j is the number of box types for supplier j. The `N * log(k_j)` term inside the sum makes this approach too slow for the given constraints, as it could lead to O(M * N * log K) in the worst case. · **Space:** O(K) or O(log K) for sorting, depending on the implementation, where K is the maximum number of box types for a single supplier.
**Pros:** Conceptually simpler than the optimal approach.
**Cons:** Inefficient due to its time complexity.; The nested loop structure, iterating through each package for each supplier, leads to a Time Limit Exceeded error on large inputs.
### Explanation
To find this "best-fit" box efficiently, we can first sort the box sizes offered by the supplier. Then, for each package, we can use binary search on the sorted box sizes to find the smallest box that is greater than or equal to the package size. We calculate the waste for this package (`box_size - package_size`) and add it to a running total for the current supplier. After doing this for all packages, we get the total waste for one supplier. We repeat this process for every supplier and keep track of the minimum total waste found. An initial check can be performed: if a supplier's largest box is smaller than the largest package, that supplier cannot be used.

```java
class Solution {
    public int minWastedSpace(int[] packages, int[][] boxes) {
        long minTotalWaste = Long.MAX_VALUE;
        int n = packages.length;
        
        Arrays.sort(packages);
        int maxPackage = packages[n - 1];

        for (int[] supplierBoxes : boxes) {
            Arrays.sort(supplierBoxes);
            int m = supplierBoxes.length;
            if (supplierBoxes[m - 1] < maxPackage) {
                continue; // This supplier cannot handle the largest package
            }

            long currentWaste = 0;
            for (int p : packages) {
                // Binary search to find the smallest box >= p (lower_bound)
                int low = 0, high = m - 1;
                int bestBoxIndex = -1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (supplierBoxes[mid] >= p) {
                        bestBoxIndex = mid;
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                currentWaste += (long)supplierBoxes[bestBoxIndex] - p;
            }
            minTotalWaste = Math.min(minTotalWaste, currentWaste);
        }

        if (minTotalWaste == Long.MAX_VALUE) {
            return -1;
        }
        return (int) (minTotalWaste % 1_000_000_007);
    }
}
```
### Algorithm
- Find the maximum package size.
- Initialize `min_waste` to a very large value (infinity).
- For each supplier `s`:
  - Sort the boxes of supplier `s`.
  - If the largest box from `s` is smaller than the maximum package size, this supplier is invalid, so we continue to the next one.
  - Initialize `current_waste` to 0.
  - For each package `p`:
    - Use binary search on the sorted boxes of `s` to find the smallest box `b` where `b >= p`.
    - Add the waste `b - p` to `current_waste`.
  - After iterating through all packages, update `min_waste = min(min_waste, current_waste)`.
- If `min_waste` is still infinity, it means no supplier could fit all packages, so return -1. Otherwise, return `min_waste` modulo 10^9 + 7.

## Sorting Packages and Boxes with Prefix Sums
The previous approach is inefficient because it re-evaluates each package for every supplier. A much faster way is to process packages in batches. If we sort both the `packages` and the `boxes` for a given supplier, we can calculate the total waste in a single pass over the boxes.
**Time:** O(N log N + S * log K + S * log N), where N is the number of packages, S is the total number of box types across all suppliers (`sum(boxes[j].length)`), and K is the maximum number of box types for a single supplier. This is efficient enough to pass the given constraints. · **Space:** O(N) to store the prefix sums of package sizes.
**Pros:** Highly efficient and optimal for the given constraints.; Avoids redundant computations by processing packages in groups, leading to a significantly better time complexity.
**Cons:** Slightly more complex to implement due to the use of prefix sums and a more involved binary search logic for grouping packages.
### Explanation
The core idea is to first sort the `packages` array once. This allows us to group packages by size. We also pre-compute the prefix sums of the package sizes, which will allow us to find the sum of sizes of any contiguous sub-array of packages in `O(1)` time. Then, for each supplier, we sort their box sizes. We iterate through the sorted box sizes. For a box of size `b`, we determine which packages will be placed in it. These are the packages that are too large for any smaller box from this supplier but small enough to fit in a box of size `b`. Since both packages and boxes are sorted, we can use binary search (`upper_bound`) on the `packages` array to find how many packages can fit into the current box size `b`. Let's say we find that packages up to index `i` can fit. If packages up to index `j` fit in the previously considered smaller box, then packages from index `j` to `i-1` will be placed in boxes of size `b`. The waste for this group of packages is `(number of packages) * b - (sum of their sizes)`. The number of packages is `i - j`, and the sum of their sizes can be found in `O(1)` using our pre-computed prefix sums. We sum up the waste for all such groups to get the total waste for the supplier and take the minimum over all suppliers.

```java
class Solution {
    public int minWastedSpace(int[] packages, int[][] boxes) {
        int n = packages.length;
        long MOD = 1_000_000_007;

        Arrays.sort(packages);

        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + packages[i];
        }

        long minTotalWaste = Long.MAX_VALUE;

        for (int[] supplierBoxes : boxes) {
            Arrays.sort(supplierBoxes);
            int m = supplierBoxes.length;

            if (supplierBoxes[m - 1] < packages[n - 1]) {
                continue;
            }

            long currentWaste = 0;
            int lastPackageIndex = 0;

            for (int boxSize : supplierBoxes) {
                if (lastPackageIndex == n) {
                    break;
                }
                
                // Find the index of the first package > boxSize (upper_bound)
                // in the range [lastPackageIndex, n).
                int lo = lastPackageIndex;
                int hi = n;
                while (lo < hi) {
                    int mid = lo + (hi - lo) / 2;
                    if (packages[mid] <= boxSize) {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }
                int currentPackageIndex = lo;

                if (currentPackageIndex > lastPackageIndex) {
                    long numPackages = currentPackageIndex - lastPackageIndex;
                    long packageSumForGroup = prefixSum[currentPackageIndex] - prefixSum[lastPackageIndex];
                    currentWaste += (numPackages * boxSize) - packageSumForGroup;
                }
                
                lastPackageIndex = currentPackageIndex;
            }
            
            minTotalWaste = Math.min(minTotalWaste, currentWaste);
        }

        if (minTotalWaste == Long.MAX_VALUE) {
            return -1;
        }

        return (int) (minTotalWaste % MOD);
    }
}
```
### Algorithm
- Sort the `packages` array.
- Compute a prefix sum array for the sorted `packages` to quickly find the sum of sizes of a range of packages.
- Initialize `min_waste` to a very large value (infinity).
- For each supplier:
  - Sort their box sizes.
  - If their largest box is smaller than the largest package, skip this supplier.
  - Initialize `current_waste = 0` and `last_package_idx = 0` (to track which packages have been assigned a box).
  - For each `box_size` in the sorted list of boxes:
    - Use binary search on `packages` to find the index `i` of the first package that is larger than the current `box_size`. The search is performed on the yet-unassigned packages.
    - The packages from `last_package_idx` to `i-1` will be placed in boxes of this size.
    - Calculate the waste for this group of packages: `(i - last_package_idx) * box_size - (sum of package sizes from last_package_idx to i-1)`. The sum is found in O(1) using the prefix sum array.
    - Add this group's waste to `current_waste`.
    - Update `last_package_idx = i`.
    - If all packages are assigned (`last_package_idx == n`), we can stop processing boxes for this supplier.
  - Update `min_waste` with `current_waste` if it's smaller.
- If `min_waste` was never updated, return -1. Otherwise, return `min_waste` modulo 10^9 + 7.

# Solutions
### Java

```java
class Solution { public int minWastedSpace ( int [] packages , int [][] boxes ) { int n = packages . length ; final long inf = 1L << 62 ; Arrays . sort ( packages ); long ans = inf ; for ( var box : boxes ) { Arrays . sort ( box ); if ( packages [ n - 1 ] > box [ box . length - 1 ]) { continue ; } long s = 0 ; int i = 0 ; for ( int b : box ) { int j = search ( packages , b , i ); s += 1L * ( j - i ) * b ; i = j ; } ans = Math . min ( ans , s ); } if ( ans == inf ) { return - 1 ; } long s = 0 ; for ( int p : packages ) { s += p ; } final int mod = ( int ) 1 e9 + 7 ; return ( int ) (( ans - s ) % mod ); } private int search ( int [] nums , int x , int l ) { int r = nums . length ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( nums [ mid ] > x ) { r = mid ; } else { l = mid + 1 ; } } return l ; } }
```

### CPP

```cpp
class Solution { public: int minWastedSpace ( vector < int >& packages , vector < vector < int >>& boxes ) { int n = packages . size (), m = boxes . size (); sort ( packages . begin (), packages . end ()); const int mod = 1e9 + 7 ; const long long inf = 1LL << 62 ; long long ans = inf ; for ( auto & box : boxes ) { sort ( box . begin (), box . end ()); if ( packages . back () > box . back ()) { continue ; } int i = 0 ; long long s = 0 ; for ( auto & b : box ) { int j = upper_bound ( packages . begin () + i , packages . end (), b ) - packages . begin (); s += 1LL * ( j - i ) * b ; i = j ; } ans = min ( ans , s ); } return ans == inf ? - 1 : ( ans - accumulate ( packages . begin (), packages . end (), 0LL )) % mod ; } };
```

### Python

```python
class Solution : def minWastedSpace ( self , packages : List [ int ], boxes : List [ List [ int ]]) -> int : mod = 10 ** 9 + 7 ans = inf packages . sort () for box in boxes : box . sort () if packages [ - 1 ] > box [ - 1 ]: continue s = i = 0 for b in box : j = bisect_right ( packages , b , lo = i ) s += ( j - i ) * b i = j ans = min ( ans , s ) if ans == inf : return - 1 return ( ans - sum ( packages )) % mod
```