Minimum space wasted from packaging

Array Binary Search Sorting Prefix Sum

33.5% acceptance

Feb 25, 2026

423

You have n packages. There are m suppliers with boxes. Find the minimum total wasted space using any single supplier. A package of size p in a box of size b wastes b-p space. Return the minimum waste mod 10^9+7, or -1 if impossible.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_wasted_space(mut packages: Vec<i32>, boxes: Vec<Vec<i32>>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    packages.sort_unstable();
    let n = packages.len();
    let _pkg_sum: i64 = packages.iter().map(|&x| x as i64).sum();

    // Prefix sums of packages
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + packages[i] as i64;
    }

    let mut best = i64::MAX;

    for mut bx in boxes {
      bx.sort_unstable();
      // Check if largest box can fit largest package
      if *bx.last().unwrap() < *packages.last().unwrap() {
        continue;
      }
      // For each box size, find packages that fit in this box but not in prev box
      let mut waste = 0i64;
      let mut prev_idx = 0usize; // exclusive end of packages handled so far

      for &b in &bx {
        if b < packages[0] { continue; } // skip boxes too small for any package
        // Find rightmost package <= b: binary search
        let right = packages.partition_point(|&x| x <= b);
        // Packages [prev_idx, right) go into this box (of size b)
        if right <= prev_idx { continue; }
        let count = (right - prev_idx) as i64;
        let sum_pkg = prefix[right] - prefix[prev_idx];
        waste += b as i64 * count - sum_pkg;
        prev_idx = right;
      }

      if waste < best { best = waste; }
    }

    if best == i64::MAX { -1 } else { (best % MOD) as i32 }
  }
}