Watch 7 video solutions for Minimum Space Wasted From Packaging, a hard level problem involving Array, Binary Search, Sorting. This walkthrough by Happy Coding has 1,495 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
[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.lengthm == boxes.length1 <= n <= 1051 <= m <= 1051 <= packages[i] <= 1051 <= boxes[j].length <= 1051 <= boxes[j][k] <= 105sum(boxes[j].length) <= 105boxes[j] are distinct.Problem Overview: You are given package sizes and multiple suppliers offering different box sizes. Each package must go into a box whose size is greater than or equal to the package. For a chosen supplier, every box size can be used multiple times. The goal is to pick a single supplier that packs all packages while minimizing total wasted space (box size minus package size).
Approach 1: Greedy with Sorting and Binary Search (O((n + m) log n), Space: O(n))
Sort the packages array first. Precompute prefix sums so you can quickly calculate the total size of any range of packages. For each supplier, sort their box sizes and skip the supplier if their largest box cannot fit the largest package. Then iterate through each box size and use binary search to find how many remaining packages can fit into that box size (using an upper bound). The wasted space for that batch equals box_size * count - sum(packages_in_range), which you compute using the prefix sums. Accumulate the waste across all box sizes for the supplier and keep the minimum. Sorting and binary searching over the package list keeps the solution efficient. This approach relies heavily on sorting, binary search, and prefix sums to avoid repeatedly scanning the package list.
Approach 2: Two-Pointer Technique with Prefix Sums (O(n log n + m log m), Space: O(n))
After sorting the packages and computing prefix sums, also sort each supplier's box sizes. Instead of running a binary search for every box, maintain a pointer over the package array. As you iterate through increasing box sizes, move the package pointer forward while the package fits in the current box. This effectively groups packages that will use the same box size. Use prefix sums to compute the total package size for the group and calculate waste in constant time. The two-pointer pattern eliminates repeated binary searches and keeps the traversal linear after sorting. The algorithm still checks every supplier and selects the minimum waste among valid ones.
Recommended for interviews: The greedy strategy with sorted packages and binary search is the approach most interviewers expect. It shows you recognize the monotonic structure created by sorting and know how to combine prefix sums with range queries. The two-pointer variant is a solid optimization and demonstrates deeper control over iteration patterns, but the core insight remains the same: process packages in sorted order and batch them into the smallest feasible box sizes.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting and Binary Search | O((n + m) log n) | O(n) | General solution. Easy to reason about using sorted packages and binary search ranges. |
| Two-Pointer Technique with Prefix Sums | O(n log n + m log m) | O(n) | When you want to avoid repeated binary searches and process packages in a single forward pass. |