1889. Minimum Space Wasted From Packaging

HardArrayBinary SearchPrefix SumSorting
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which data structure is used to implement priority queue?

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:

  1. 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.

  2. 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) to box[-1] (the largest box size for the current supplier).

    • Initialize Variables: Before traversing the box sizes, we initialize s to 0, which will hold the cumulative wasted space, and i to 0, which will track the current index in the packages array.

  3. Binary Search for Package Placement: For each box size b of the current supplier:

    • Utilize bisect_right(packages, b, lo=i) to find the index j in the sorted packages array. This index j is such that all packages in packages[i:j] fit in the box size b. The lo=i argument ensures the binary search starts from the current index i in the packages array.

    • Calculate Wasted Space: Add (j - i) * b to s, which represents the space taken by the boxes that could have been filled with packages in packages[i:j].

    • Update Package Counter: Assign j to i to update the index in packages for the next iteration.

  4. 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 answer ans. If so, update ans to s.

  5. Final Check: If after examining all suppliers, ans remains math.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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Example 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.

  • 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 and i = 0.

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 index j = 1 in packages.
    • Wasted space: (1 - 0) * 3 = 3.
    • Update i to 1.

    For box size b = 6:

    • With bisect_right(packages, 6, lo=1), we get j = 2.
    • Wasted space: (2 - 1) * 6 = 6 and now s = 3 + 6 = 9.
    • Update i to 2.

    For box size b = 9:

    • With bisect_right(packages, 9, lo=2), we get j = 3.
    • Wasted space: (3 - 2) * 9 = 9 and now s = 9 + 9 = 18.
    • i becomes 3, indicating all packages are placed.

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 is 18.

    • Calculating the total wasted space: ans - sum(packages) = 18 - (3 + 5 + 8) = 18 - 16 = 2.
    • The result modulo 10^9 + 7 is still 2.

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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which two pointer techniques do you use to check if a string is a palindrome?

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed as follows:

  • Sorting the packages list takes O(NlogN) time, with N being the length of the packages.
  • The for loop iterates through each box in boxes. Let's say there are M boxes.
  • Each box is also sorted, taking O(BlogB) time, where B is the maximum number of items in a single box.
  • The inner for loop iterates through each item b in the box. The bisect_right function is also called inside this loop, which works in O(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 of packages, thus the combined complexity of the loop with the bisect_right is O(BlogN). However, since i = j assigns the new starting index after every bisect, it ensures that each package is considered only once across all boxes. Hence, the complexity for all boxes together should be O(BlogN), not O(M*B*logN).
  • The overall time complexity is O(NlogN + M*B*logN) since the sorting of the packages and the boxes are the dominating factors.

Space Complexity

The space complexity of the code can be determined as follows:

  • The sorted packages list and box list require additional space, which contributes to the space complexity. This could be, in the worst case, O(N + B) respective space for sorted packages and the largest box.
  • The variables ans, s, i, j, and mod use constant space, which does not depend on the input size, hence contributing O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Binary Search Speedrun

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

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

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ