Scale Engineer

Minimum Space Wasted From Packaging

Hard
#1725Time: 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.1 company
Patterns
Prefix Sum
Algorithms
Binary SearchSorting
Data structures
Array
Companies
Two Sigma

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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);    }}

Complexity

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.

Trade-offs

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.

Solutions

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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem