LeetCode 1889: Minimum Space Wasted From Packaging

Sort and linear search

For each supplier we can find the minimum waste by trying to fit a package in the smallest box possible. We take min across all suppliers.

If the longest box list has length $b$ , then time: $\mathcal{O}( n \cdot \lg{n} + m \cdot \left( b \cdot \lg{b} + (b + n) \right) )$ . Space: that of sorting.

class Solution:
    def min_waste_for_supplier(self, packages, boxes) -> float:
        MOD = pow(10, 9) + 7

        boxes.sort()
        # No box for largest package
        if packages[-1] > boxes[-1]:
            return float('inf')

        waste = 0
        i = 0
        for p in packages:
            # Find a large enough box
            while i < len(boxes) and p > (b := boxes[i]):
                i += 1
            waste = (waste + (b - p)) % MOD
        return waste

    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        packages.sort()

        min_waste = min(
            self.min_waste_for_supplier(packages, box_list)
            for box_list in boxes
        )

        return min_waste if min_waste != float('inf') else -1

Sort and binary search

In min_waste_for_supplier(), instead of trying to find a box for each package, we could try finding which packages can be fit into a box using binary search.

Time: $\mathcal{O}( n \cdot \lg{n} + m \cdot \left( b \cdot \lg{b} + b \cdot \lg{n} \right) )$ . The difference with linear search’s complexity is: $m \cdot (b+n)$ vs. $m \cdot (b \cdot \lg{n})$ .

Space: that of sorting.

class Solution:
    # fit packages[start:lo] in this box
    def find_insert_index(self, box, packages, start) -> int:
        lo = start
        hi = len(packages)-1
        while lo <= hi:
            mid = (lo + hi) // 2
            if packages[mid] > box:
                hi = mid-1
            else:
                lo = mid+1
        return lo

    def min_waste_for_supplier(self, packages, boxes, package_space) -> float:
        MOD = pow(10, 9) + 7

        boxes.sort()
        # No box for largest package
        if packages[-1] > boxes[-1]:
            return float('inf')

        start, used_space = 0, 0
        for box_size in boxes:
            end = self.find_insert_index( box_size, packages, start )
            package_count = end-start
            used_space += (package_count * box_size)
            if end >= len(packages):
                break
            start = end
        
        return used_space - package_space


    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        MOD = pow(10, 9) + 7
        packages.sort()
        package_space = sum(packages)

        min_waste = min(
            self.min_waste_for_supplier(packages, box_list, package_space)
            for box_list in boxes
        )

        return min_waste % MOD if min_waste != float('inf') else -1

unreasonably effective