1889. Minimum Space Wasted From Packaging
Problem Description
In this problem, we are given n
packages with different sizes, and we aim to place each package into a box from one of m
suppliers. Each supplier supplies an unlimited number of boxes of various sizes. A package can fit in a box if its size doesn't exceed the size of the box. The goal is to minimize the total wasted space, which is the sum of the differences between the sizes of the boxes and the packages they contain.
The sizes of the packages are given in an integer array packages
, and the suppliers' boxes' sizes are given in a 2D integer array boxes
. Our task is to select boxes from one supplier such that the total wasted space is minimized. If it's not possible to fit all packages into boxes, we should return -1
. Otherwise, we compute the total wasted space and return it modulo 10^9 + 7
, which is a way of keeping the returned value within a reasonable range for very large numbers.
An example is provided where we have packages of sizes [2,3,5]
and a supplier with box sizes [4,8]
. The smallest total wasted space in this scenario is 6
, achieved by placing the packages into the respective boxes such that the package of size 2
and the package of size 3
go into boxes of size 4
, and the package of size 5
goes into a box of size 8
.
The problem requires optimization and an efficient approach to checking all possible suppliers while avoiding unnecessary calculations to find the solution within a reasonable time.
Intuition
The solution to this problem is based on sorting and binary search. Firstly, we recognize that to fit all packages from a supplier's boxes, the largest box from the supplier must be equal to or greater than the largest package size. If that's the case, we can then proceed to calculate the total wasted space using the boxes from this supplier.
The intuition behind the sorting of both "packages" and the "boxes" array for each supplier is that it aligns the packages in ascending order, making it easier to find the smallest box in which each package will fit using binary search. We use the bisect_right
function from the bisect
module (in Python) for this purpose, which finds the insertion point in the array to the right of the target value, efficiently determining the number of packages a specific box can accommodate.
By iterating over each box size for the chosen supplier, we can keep track of how many packages have been placed (i
represents the index within the package array), and how much wasted space has been incurred thus far (s
is the cumulative waste). For each box size b
, we find the index j
up to which we can place the packages starting from index i
. Then we simply multiply b
with the number of packages that can fit in this box (j - i
) and add it to the total waste accumulator s
.
At each step, we compare the total waste s
with the best answer found so far (ans
). If s
is smaller, we update ans
.
If after checking all possible suppliers, ans
still holds the value inf
, it implies that it was not possible to fit all packages into any supplier's boxes, and we return -1
. If we found a valid configuration, we return ans - sum(packages)
(this is the total wasted space) modulo 10^9 + 7
.
The solution approach efficiently narrows down suppliers and calculates waste without unnecessary checks or iterations, hence optimizing the process.
Learn more about Binary Search, Prefix Sum and Sorting patterns.
Solution Approach
The solution involves two major components: sorting and binary search. These algorithms are crucial in optimizing the process to minimize wasted space. The steps for the solution are implemented as follows:
-
Sort Package Sizes: We begin by sorting the array
packages
in non-decreasing order. This is crucial for the binary search step as binary search requires a sorted array to function correctly. -
Iterate Over Suppliers: For each supplier in
boxes
, we proceed with the following steps:-
Sort Box Sizes: Sort the array of box sizes for the current supplier. This not only assists with the binary search but also ensures that we can check from the smallest to the largest box when trying to place packages, which helps in finding the optimal fit.
-
Check Largest Box: Before calculating the wasted space for a supplier, check if the largest box of the supplier is at least as large as the largest package size. If not, we cannot use this supplier, as not all packages can fit. This is done by comparing
packages[-1]
(the largest package, since the array is sorted) tobox[-1]
(the largest box size for the current supplier). -
Initialize Variables: Before traversing the box sizes, we initialize
s
to0
, which will hold the cumulative wasted space, andi
to0
, which will track the current index in thepackages
array.
-
-
Binary Search for Package Placement: For each box size
b
of the current supplier:-
Utilize
bisect_right(packages, b, lo=i)
to find the indexj
in the sortedpackages
array. This indexj
is such that all packages inpackages[i:j]
fit in the box sizeb
. Thelo=i
argument ensures the binary search starts from the current indexi
in thepackages
array. -
Calculate Wasted Space: Add
(j - i) * b
tos
, which represents the space taken by the boxes that could have been filled with packages inpackages[i:j]
. -
Update Package Counter: Assign
j
toi
to update the index inpackages
for the next iteration.
-
-
Update Answer: After iterating through all the box sizes for the current supplier, check if the accumulated wasted space
s
is less than the current answerans
. If so, updateans
tos
. -
Final Check: If after examining all suppliers,
ans
remainsmath.inf
, it's impossible to fit all packages into boxes, and we return-1
. Otherwise:-
Calculate Total Wasted Space: Subtract the sum of package sizes from
ans
to get the total wasted space. -
Modulo Operation: Return the result of this subtraction modulo
10^9 + 7
to handle the case of large numbers, as required by the problem statement.
-
The patterns used in this solution, such as sorting and binary search, are well-known for their efficiency. Sorting the arrays allows for the use of binary search, which is an efficient algorithm with a time complexity of O(log n)
for finding elements or insertion points in a sorted array. These algorithms, combined with a careful approach to examine each supplier and efficiently calculate the wasted space, allow the solution to minimize the total wasted space while fitting the packages into boxes optimally.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach using the problem's logic.
Suppose we have packages
of sizes [3,5,8]
and boxes
from suppliers [[2,4,7],[3,6,9]]
. The goal is to find the minimum total wasted space by optimally fitting these packages into the boxes provided by one of the suppliers.
Step 1: Sort Package Sizes
- We sort the
packages
array:[3, 5, 8]
. Itās already sorted in this example.
Step 2: Iterate Over Suppliers
-
For the first supplier
boxes[0]
, the box sizes are[2,4,7]
.Step 2.1: Sort Box Sizes
- Sort the box sizes:
[2,4,7]
.
Step 2.2: Check Largest Box
- We check if the largest box size (7) is at least as large as the largest package size (8). It is not, so we cannot use this supplier since not all packages would fit.
- Sort the box sizes:
-
For the second supplier
boxes[1]
, the box sizes are[3,6,9]
.Step 2.1: Sort Box Sizes
- Sort the box sizes:
[3,6,9]
(also already sorted).
Step 2.2: Check Largest Box
- The largest box size (9) is larger than the largest package size (8), so we can continue with this supplier.
Step 2.3: Initialize Variables
- Set
s = 0
andi = 0
.
- Sort the box sizes:
Step 3: Binary Search for Package Placement
-
We iterate over the boxes
[3,6,9]
from the current supplier.For box size
b = 3
:- Using binary search with
bisect_right(packages, 3, lo=0)
, we find indexj = 1
inpackages
. - Wasted space:
(1 - 0) * 3 = 3
. - Update
i
to1
.
For box size
b = 6
:- With
bisect_right(packages, 6, lo=1)
, we getj = 2
. - Wasted space:
(2 - 1) * 6 = 6
and nows = 3 + 6 = 9
. - Update
i
to2
.
For box size
b = 9
:- With
bisect_right(packages, 9, lo=2)
, we getj = 3
. - Wasted space:
(3 - 2) * 9 = 9
and nows = 9 + 9 = 18
. i
becomes3
, indicating all packages are placed.
- Using binary search with
Step 4: Update Answer
- As this is the first supplier that can fit all packages, we set
ans = 18
.
Step 5: Final Check
-
After checking all suppliers, the minimum
ans
found is18
.- Calculating the total wasted space:
ans - sum(packages) = 18 - (3 + 5 + 8) = 18 - 16 = 2
. - The result modulo
10^9 + 7
is still2
.
- Calculating the total wasted space:
Therefore, for this example, the minimum total wasted space is 2
, and that is achieved by using the boxes from the second supplier.
Solution Implementation
1from bisect import bisect_right
2from math import inf
3
4class Solution:
5 def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
6 MODULO = 10**9 + 7 # Constant for modulo operation
7 answer = inf # Initializing the answer with infinity representing large number
8 packages.sort() # Sort the packages to perform binary search
9
10 # Iterate over the list of boxes
11 for box in boxes:
12 box.sort() # Sort the box sizes
13 # If the largest package can't fit in the largest box, skip this set of boxes
14 if packages[-1] > box[-1]:
15 continue
16
17 space_used = 0 # Track space used by current set of boxes
18 package_index = 0 # Current index in packages list
19
20 # Iterate over the boxes to determine how much space is used
21 for box_size in box:
22 # Find the rightmost package that fits in the current box
23 next_package_index = bisect_right(packages, box_size, lo=package_index)
24 # Accumulate the total space used by the current box
25 space_used += (next_package_index - package_index) * box_size
26 # Advance the starting index of packages for the next box
27 package_index = next_package_index
28
29 # Store the minimum space used found so far
30 answer = min(answer, space_used)
31
32 # If no answer was found (no boxes can contain all packages), return -1
33 if answer == inf:
34 return -1
35
36 # Return the wasted space as (space used - space of packages) modulo MODULO
37 return (answer - sum(packages)) % MODULO
38
1class Solution {
2 public int minWastedSpace(int[] packages, int[][] boxes) {
3 // Sort the packages for binary search
4 Arrays.sort(packages);
5 int packageCount = packages.length;
6 // Define a high value for initial comparison
7 final long INF = Long.MAX_VALUE;
8 long minWaste = INF;
9
10 for (int[] box : boxes) {
11 // Sort each type of box since we need to handle them sequentially
12 Arrays.sort(box);
13 // Skip the box type if the largest box cannot hold the largest package
14 if (packages[packageCount - 1] > box[box.length - 1]) {
15 continue;
16 }
17 long currentWaste = 0;
18 int startIndex = 0;
19
20 // Calculate the waste for this box type
21 for (int size : box) {
22 int endIndex = upperBound(packages, size, startIndex);
23 currentWaste += 1L * (endIndex - startIndex) * size;
24 startIndex = endIndex;
25 }
26
27 // Update the minimum waste if the current one is smaller
28 minWaste = Math.min(minWaste, currentWaste);
29 }
30
31 // Return -1 if no box type can accommodate all packages
32 if (minWaste == INF) {
33 return -1;
34 }
35 // Calculate the total size of all packages
36 long totalPackageSize = 0;
37 for (int p : packages) {
38 totalPackageSize += p;
39 }
40
41 // Modulo for the final result to avoid number overflow
42 final int MOD = (int) 1e9 + 7;
43 return (int) ((minWaste - totalPackageSize) % MOD);
44 }
45
46 // Custom binary search function to find the upper bound
47 private int upperBound(int[] nums, int target, int left) {
48 int right = nums.length;
49 while (left < right) {
50 int mid = left + (right - left) / 2;
51 if (nums[mid] > target) {
52 right = mid;
53 } else {
54 left = mid + 1;
55 }
56 }
57 return left;
58 }
59}
60
1class Solution {
2public:
3 int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
4 int numOfPackages = packages.size(); // Number of packages to be shipped
5 int numOfBoxTypes = boxes.size(); // Number of different types of box sets available
6 sort(packages.begin(), packages.end()); // Sort packages by size for efficient comparisons
7 const int MOD = 1e9 + 7; // The modulo value to prevent integer overflow
8 const long long INF = 1LL << 62; // A large number to represent infinity for initial comparison
9 long long minWaste = INF; // Initialize minimum waste space to infinity
10
11 // Iterate through each type of box set
12 for (auto& boxSet : boxes) {
13 sort(boxSet.begin(), boxSet.end()); // Sort the boxes in the current set by size
14 if (packages.back() > boxSet.back()) { // Skip if the largest box cannot fit the largest package
15 continue;
16 }
17
18 int currentPackageIndex = 0; // Index for the current package to be considered
19 long long currentWasteSpace = 0; // Space wasted for the current box set
20
21 // Iterate through boxes in the current set
22 for (auto& boxSize : boxSet) {
23 // Find the index beyond which all packages become too large for the current boxSize
24 int nextPackageIndex = upper_bound(packages.begin() + currentPackageIndex, packages.end(), boxSize) - packages.begin();
25
26 // Calculate space waste by multiplying the number of packages that fit by box size
27 currentWasteSpace += 1LL * (nextPackageIndex - currentPackageIndex) * boxSize;
28
29 // Update the index to the next package not covered by the current boxSize
30 currentPackageIndex = nextPackageIndex;
31 }
32
33 // Update minimum waste space if current set is better
34 minWaste = min(minWaste, currentWasteSpace);
35 }
36
37 // If minWaste is still INF, no box set can fit all packages; otherwise, calculate total waste
38 return minWaste == INF ? -1 : (minWaste - accumulate(packages.begin(), packages.end(), 0LL)) % MOD; // Calculate total waste space and return modulo
39 }
40};
41
1function minWastedSpace(packages: number[], boxSizes: number[][]): number {
2 const packageCount: number = packages.length;
3 const INF: number = Infinity; // Using Infinity to represent an unattainable high value
4 packages.sort((a, b) => a - b); // Sort the packages in ascending order
5 let minimumWaste: number = INF; // Minimal waste initialized to Infinity
6
7 for (const boxSize of boxSizes) {
8 boxSize.sort((a, b) => a - b); // Sort each set of boxes in ascending order
9
10 // If the largest package won't fit in the largest box, skip this set
11 if (packages[packageCount - 1] > boxSize[boxSize.length - 1]) {
12 continue;
13 }
14
15 let spaceUsed: number = 0;
16 let packageIndex: number = 0;
17
18 for (const box of boxSize) {
19 const endIndex = upperBound(packages, box, packageIndex);
20 spaceUsed += (endIndex - packageIndex) * box; // Compute space used for box size
21 packageIndex = endIndex; // Update the index of packages to the next starting point
22 }
23
24 minimumWaste = Math.min(minimumWaste, spaceUsed); // Update the minimum waste
25 }
26
27 // If no box set fits, return -1
28 if (minimumWaste === INF) {
29 return -1;
30 }
31
32 // Sum the size of all packages
33 const totalPackageSize = packages.reduce((sum, packageSize) => sum + packageSize, 0);
34
35 // Calculate the result as (used space - total package size) modulo 1,000,000,007
36 return (minimumWaste - totalPackageSize) % 1000000007;
37}
38
39// Helper function to find the index of the first element greater than x
40function upperBound(nums: number[], x: number, low: number): number {
41 let high: number = nums.length;
42
43 // Perform binary search for the upper bound index
44 while (low < high) {
45 const mid = (low + high) >> 1; // Equivalent to Math.floor((low + high) / 2)
46 if (nums[mid] > x) {
47 high = mid;
48 } else {
49 low = mid + 1;
50 }
51 }
52
53 return low; // Return the upper bound index
54}
55
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed as follows:
- Sorting the
packages
list takesO(NlogN)
time, withN
being the length of the packages. - The
for
loop iterates through each box inboxes
. Let's say there areM
boxes. - Each
box
is also sorted, takingO(BlogB)
time, whereB
is the maximum number of items in a single box. - The inner
for
loop iterates through each itemb
in the box. Thebisect_right
function is also called inside this loop, which works inO(logN)
time complexity for each b because it uses a binary search algorithm.- In the worst case, every call to
bisect_right
can iterate over all elements ofpackages
, thus the combined complexity of the loop with thebisect_right
isO(BlogN)
. However, sincei = j
assigns the new starting index after everybisect
, it ensures that each package is considered only once across all boxes. Hence, the complexity for all boxes together should beO(BlogN)
, notO(M*B*logN)
.
- In the worst case, every call to
- The overall time complexity is
O(NlogN + M*B*logN)
since the sorting of thepackages
and the boxes are the dominating factors.
Space Complexity
The space complexity of the code can be determined as follows:
- The sorted
packages
list andbox
list require additional space, which contributes to the space complexity. This could be, in the worst case,O(N + B)
respective space for sortedpackages
and the largestbox
. - The variables
ans
,s
,i
,j
, andmod
use constant space, which does not depend on the input size, hence contributingO(1)
space. - Consequently, the total space complexity is
O(N + B)
.
Note: inf
and mod
are constants defined in the global namespace, and their space is considered as O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!