1889. Minimum Space Wasted From Packaging LeetCode Solution

In this guide, you will get 1889. Minimum Space Wasted From Packaging LeetCode Solution with the best time and space complexity. The solution to Minimum Space Wasted From Packaging problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Space Wasted From Packaging solution in C++
Minimum Space Wasted From Packaging solution in Java
Minimum Space Wasted From Packaging solution in Python
Additional Resources

1889. Minimum Space Wasted From Packaging LeetCode Solution image

Problem Statement of Minimum Space Wasted From Packaging

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.

Complexity Analysis

Time Complexity: O(\texttt{sort}(n) + \texttt{sort}(m) + m\log n), where n = |\texttt{packages}| and m = |\texttt{boxes}|
Space Complexity: O(\texttt{sort}(n) + \texttt{sort}(m))

1889. Minimum Space Wasted From Packaging LeetCode Solution in C++

class Solution {
 public:
  int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
    constexpr int kMod = 1'000'000'007;
    constexpr long kInf = 1e11;
    const long packagesSum = accumulate(packages.begin(), packages.end(), 0L);
    long minBoxesSum = kInf;

    ranges::sort(packages);

    for (vector<int>& box : boxes) {
      ranges::sort(box);
      if (box.back() < packages.back())
        continue;
      long accu = 0;
      long i = 0;
      for (const int b : box) {
        const long j = firstGreaterEqual(packages, b + 1);
        accu += b * (j - i);
        i = j;
      }
      minBoxesSum = min(minBoxesSum, accu);
    }

    return minBoxesSum == kInf ? -1 : (minBoxesSum - packagesSum) % kMod;
  }

 private:
  int firstGreaterEqual(const vector<int>& arr, int target) {
    return ranges::lower_bound(arr, target) - arr.begin();
  }
};
/* code provided by PROGIEZ */

1889. Minimum Space Wasted From Packaging LeetCode Solution in Java

class Solution {
  public int minWastedSpace(int[] packages, int[][] boxes) {
    final int kMod = 1_000_000_007;
    final long kInf = (long) 1e11;
    final long packagesSum = Arrays.stream(packages).mapToLong(p -> p).sum();
    long minBoxesSum = kInf;

    Arrays.sort(packages);

    for (int[] box : boxes) {
      Arrays.sort(box);
      if (box[box.length - 1] < packages[packages.length - 1])
        continue;
      long accu = 0;
      long i = 0;
      for (final int b : box) {
        final long j = firstGreaterEqual(packages, b + 1);
        accu += b * (j - i);
        i = j;
      }
      minBoxesSum = Math.min(minBoxesSum, accu);
    }

    return minBoxesSum == kInf ? -1 : (int) ((minBoxesSum - packagesSum) % kMod);
  }

  private int firstGreaterEqual(int[] arr, int target) {
    int l = 0;
    int r = arr.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (arr[m] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}
// code provided by PROGIEZ

1889. Minimum Space Wasted From Packaging LeetCode Solution in Python

class Solution:
  def minWastedSpace(self, packages: list[int], boxes: list[list[int]]) -> int:
    ans = math.inf

    packages.sort()

    for box in boxes:
      box.sort()
      if box[-1] < packages[-1]:
        continue
      accu = 0
      i = 0
      for b in box:
        j = bisect.bisect(packages, b, i)
        accu += b * (j - i)
        i = j
      ans = min(ans, accu)

    return -1 if ans == math.inf else (ans - sum(packages)) % int(1e9 + 7)
 # code by PROGIEZ