LeetCode 1889 - Minimum Space Wasted From Packaging

The problem gives us a list of package sizes and several suppliers. Each supplier offers an unlimited number of boxes, but only in certain fixed sizes. We must choose exactly one supplier and pack every package using only the box sizes that supplier provides.

leetcodehardarraybinary-searchsortingprefix-sum

LeetCode Problem 1889

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Sorting, Prefix Sum

Solution

Problem Understanding

The problem gives us a list of package sizes and several suppliers. Each supplier offers an unlimited number of boxes, but only in certain fixed sizes. We must choose exactly one supplier and pack every package using only the box sizes that supplier provides.

Each package must go into a single box whose size is greater than or equal to the package size. The wasted space for a package is:

$$\text{box size} - \text{package size}$$

Our goal is to minimize the total wasted space across all packages.

The important restriction is that we may only use one supplier. We cannot mix boxes from different suppliers.

The input consists of:

  • packages, an array of package sizes
  • boxes, where boxes[j] contains the box sizes provided by supplier j

The output is the minimum possible wasted space, or -1 if no supplier can fit every package.

The constraints are large:

  • Up to 10^5 packages
  • Total number of box sizes across all suppliers is also up to 10^5

These limits immediately rule out any quadratic style solution. We need an approach close to:

$$O(n \log n)$$

or

$$O((n + \text{total boxes}) \log n)$$

The constraints also strongly suggest sorting and binary search.

Several edge cases are important:

  • A supplier may not have a box large enough for the largest package
  • Multiple packages may fit into the same box size category
  • Suppliers may provide box sizes in arbitrary order
  • Some suppliers may have many redundant box sizes
  • The answer can become very large, so we must return it modulo $10^9 + 7$

Approaches

Brute Force Approach

A straightforward approach is to try every supplier independently.

For each supplier:

  1. For every package, search for the smallest valid box
  2. Compute the waste contributed by that package
  3. Sum all wastes

If we linearly scan box sizes for every package, the complexity becomes extremely large.

Even if we sort each supplier's boxes and binary search for each package, the total complexity becomes:

$$O\left(\sum_j n \log b_j\right)$$

where:

  • $n$ is the number of packages
  • $b_j$ is the number of box sizes for supplier $j$

Since both values can be as large as $10^5$, this approach is too slow.

Key Insight

The important observation is that once packages are sorted, packages assigned to the same box size form a contiguous range.

Suppose a supplier provides sorted box sizes:

$$[4, 8, 10]$$

Then:

  • all packages up to size 4 can use box 4
  • the next range can use box 8
  • the remaining range can use box 10

Instead of processing packages one by one, we process them in groups.

We can use binary search to determine how many packages fit into each box size.

To efficiently compute the total package sizes in a range, we use a prefix sum array.

This transforms repeated per-package work into efficient range calculations.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force $O(\sum n \log b_j)$ $O(1)$ Binary search each package independently
Optimal $O(n \log n + \sum b_j \log n)$ $O(n)$ Sort packages once, use prefix sums and grouped assignment

Algorithm Walkthrough

  1. Sort the packages array.

Sorting is essential because it allows us to assign contiguous ranges of packages to a particular box size. 2. Build a prefix sum array for package sizes.

Let:

$$prefix[i]$$

represent the sum of the first i packages.

This allows us to compute the sum of any package range in constant time. 3. Track the largest package size.

If a supplier's largest box is smaller than the largest package, that supplier is impossible to use. 4. Process each supplier independently.

For each supplier:

  • Sort its box sizes
  • Skip it if its largest box cannot fit the largest package
  1. Greedily assign packages to box sizes.

Maintain a pointer start representing the first unassigned package.

For each box size:

  • Use binary search to find the rightmost package that fits
  • Suppose packages from start to end - 1 fit
  1. Compute waste for that group.

If count = end - start, then:

$$\text{space used} = \text{box size} \times count$$

and:

$$\text{actual package sum} = prefix[end] - prefix[start]$$

Therefore:

$$\text{waste} = (\text{box size} \times count) - (\text{package sum})$$ 7. Accumulate the waste and continue.

Move start = end and process the next box size. 8. Track the minimum waste across all suppliers. 9. Return the minimum modulo $10^9 + 7$.

If no supplier can fit all packages, return -1.

Why it works

Because both packages and box sizes are sorted, assigning the smallest possible box to every package is always optimal for a fixed supplier. Any larger box would only increase wasted space.

The binary search step correctly partitions packages into contiguous groups that fit each box size. Prefix sums ensure we compute the total wasted space for each group exactly.

Therefore, the algorithm computes the minimum possible waste for every supplier and returns the global minimum.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        MOD = 10**9 + 7

        packages.sort()
        n = len(packages)

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + packages[i]

        largest_package = packages[-1]

        answer = float("inf")

        for supplier_boxes in boxes:
            supplier_boxes.sort()

            if supplier_boxes[-1] < largest_package:
                continue

            waste = 0
            start = 0

            for box_size in supplier_boxes:
                end = bisect_right(packages, box_size, start)

                if end > start:
                    count = end - start
                    package_sum = prefix[end] - prefix[start]

                    waste += box_size * count - package_sum

                    start = end

                if start == n:
                    break

            answer = min(answer, waste)

        return answer % MOD if answer != float("inf") else -1

The implementation begins by sorting the packages. This enables grouped processing with binary search.

The prefix sum array stores cumulative package sizes. With it, we can compute the sum of any package interval in constant time.

For each supplier, we first sort the available box sizes. If the supplier cannot fit the largest package, we immediately skip that supplier.

The variable start tracks the first package not yet assigned to a box. For each box size, bisect_right finds the first package index greater than the box size. Everything before that index can fit into the current box.

Using the prefix sums, we compute the waste contributed by the entire group at once rather than processing packages individually.

Finally, we keep the minimum waste among all suppliers and return it modulo $10^9 + 7$.

Go Solution

package main

import (
	"math"
	"sort"
)

func minWastedSpace(packages []int, boxes [][]int) int {
	const MOD int64 = 1e9 + 7

	sort.Ints(packages)

	n := len(packages)

	prefix := make([]int64, n+1)
	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + int64(packages[i])
	}

	largestPackage := packages[n-1]

	answer := int64(math.MaxInt64)

	for _, supplierBoxes := range boxes {
		sort.Ints(supplierBoxes)

		if supplierBoxes[len(supplierBoxes)-1] < largestPackage {
			continue
		}

		var waste int64 = 0
		start := 0

		for _, boxSize := range supplierBoxes {
			end := sort.Search(
				n,
				func(i int) bool {
					return packages[i] > boxSize
				},
			)

			if end < start {
				end = start
			}

			if end > start {
				count := int64(end - start)
				packageSum := prefix[end] - prefix[start]

				waste += int64(boxSize)*count - packageSum

				start = end
			}

			if start == n {
				break
			}
		}

		if waste < answer {
			answer = waste
		}
	}

	if answer == int64(math.MaxInt64) {
		return -1
	}

	return int(answer % MOD)
}

The Go implementation follows the same logic as the Python version.

One important difference is integer handling. Since the waste can become very large, the implementation uses int64 for prefix sums and waste calculations to avoid overflow.

Go does not provide a direct equivalent of Python's bisect_right, so we use sort.Search to find the first index where packages[i] > boxSize.

Slices are used naturally for arrays, and sorting is performed with sort.Ints.

Worked Examples

Example 1

packages = [2,3,5]
boxes = [[4,8],[2,8]]

Sorted packages:

[2,3,5]

Prefix sums:

Index Prefix Sum
0 0
1 2
2 5
3 10

Supplier 1: [4,8]

Box Size Packages Covered Count Waste
4 [2,3] 2 (4×2) - (2+3) = 3
8 [5] 1 (8×1) - 5 = 3

Total waste:

3 + 3 = 6

Supplier 2: [2,8]

Box Size Packages Covered Count Waste
2 [2] 1 0
8 [3,5] 2 16 - 8 = 8

Total waste:

8

Minimum answer:

6

Example 2

packages = [2,3,5]
boxes = [[1,4],[2,3],[3,4]]

Largest package:

5

Supplier maximum box sizes:

Supplier Largest Box
[1,4] 4
[2,3] 3
[3,4] 4

None can fit package 5.

Answer:

-1

Example 3

packages = [3,5,8,10,11,12]
boxes = [[12],[11,9],[10,5,14]]

Sorted packages:

[3,5,8,10,11,12]

Supplier [12]

Every package uses box 12.

Waste:

(12-3) + (12-5) + (12-8) + (12-10) + (12-11) + (12-12)
= 9 + 7 + 4 + 2 + 1 + 0
= 23

Supplier [11,9]

Largest box is 11, cannot fit package 12.

Skip supplier.

Supplier [10,5,14]

Sorted boxes:

[5,10,14]
Box Size Packages Covered Waste
5 [3,5] 2
10 [8,10] 2
14 [11,12] 5

Total:

2 + 2 + 5 = 9

Minimum answer:

9

Complexity Analysis

Measure Complexity Explanation
Time $O(n \log n + \sum b_j \log n)$ Sorting packages once, then binary searching package ranges for each box size
Space $O(n)$ Prefix sum array storage

The dominant cost comes from sorting the packages and performing binary searches for each box size across all suppliers.

The total number of box sizes across all suppliers is bounded by 10^5, so the overall complexity remains efficient for the problem constraints.

Test Cases

from typing import List

class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        from bisect import bisect_right

        MOD = 10**9 + 7

        packages.sort()
        n = len(packages)

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + packages[i]

        answer = float("inf")

        for supplier_boxes in boxes:
            supplier_boxes.sort()

            if supplier_boxes[-1] < packages[-1]:
                continue

            waste = 0
            start = 0

            for box_size in supplier_boxes:
                end = bisect_right(packages, box_size, start)

                if end > start:
                    count = end - start
                    waste += (
                        box_size * count
                        - (prefix[end] - prefix[start])
                    )
                    start = end

                if start == n:
                    break

            answer = min(answer, waste)

        return answer % MOD if answer != float("inf") else -1

sol = Solution()

assert sol.minWastedSpace(
    [2,3,5],
    [[4,8],[2,8]]
) == 6  # basic example

assert sol.minWastedSpace(
    [2,3,5],
    [[1,4],[2,3],[3,4]]
) == -1  # impossible case

assert sol.minWastedSpace(
    [3,5,8,10,11,12],
    [[12],[11,9],[10,5,14]]
) == 9  # multiple suppliers

assert sol.minWastedSpace(
    [1],
    [[1]]
) == 0  # exact fit

assert sol.minWastedSpace(
    [1,2,3],
    [[3]]
) == 3  # all packages use same box

assert sol.minWastedSpace(
    [5,5,5],
    [[5],[6]]
) == 0  # repeated package sizes

assert sol.minWastedSpace(
    [2,4,6],
    [[3,7]]
) == 5  # mixed assignment

assert sol.minWastedSpace(
    [10],
    [[9],[10],[11]]
) == 0  # choose optimal supplier

assert sol.minWastedSpace(
    [100000],
    [[100000]]
) == 0  # maximum value boundary

assert sol.minWastedSpace(
    [1,2,3,4,5],
    [[5],[6],[7]]
) == 0  # perfect fit available
Test Why
[2,3,5] with [[4,8],[2,8]] Validates standard grouping logic
Impossible supplier set Ensures -1 is returned correctly
Multiple suppliers Verifies minimum supplier selection
Single package exact fit Smallest valid input
Single box size Tests grouped assignment
Duplicate package sizes Ensures repeated values work correctly
Mixed assignment Verifies binary search partitioning
Multiple valid suppliers Ensures optimal supplier chosen
Maximum package value Boundary constraint validation
Perfect fit supplier Confirms zero waste handling

Edge Cases

One important edge case occurs when no supplier can fit the largest package. A naive implementation might still attempt calculations and produce incorrect results. The implementation explicitly checks whether the supplier's largest box is at least as large as the largest package before processing that supplier.

Another important case is when many packages share the same size. Binary search boundaries can become tricky when duplicates exist. Using bisect_right ensures all packages less than or equal to the current box size are grouped correctly.

A third edge case involves suppliers with redundant or poorly ordered box sizes. Since each supplier's box sizes are sorted before processing, the algorithm always assigns packages using the smallest feasible box first, which guarantees minimum waste for that supplier.

A final edge case is extremely large waste values. Because package counts and box sizes can both reach 10^5, intermediate sums can exceed 32 bit integer limits. The Python implementation naturally handles large integers, while the Go solution explicitly uses int64 to prevent overflow.