Skip to main content
Talentd

Minimum Space Wasted From Packaging - Solution & Explanation

HardArrayBinary SearchSortingPrefix Sum12 min readAsked at: Amazon, IMC, Two Sigma
Practice this problem

Problem Statement

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.

  • For example, if you have to fit packages with sizes [2,3,5] and the supplier offers boxes of sizes [4,8], you can fit the packages of size-2 and size-3 into two boxes of size-4 and the package with size-5 into a box of size-8. This would result in a waste of (4-2) + (4-3) + (8-5) = 6.

Return the minimum total wasted space by choosing the box supplier optimally, or -1 if it is impossible to fit all the packages inside boxes. Since the answer may be large, return it modulo 109 + 7.

 

Example 1:

Input: packages = [2,3,5], boxes = [[4,8],[2,8]]
Output: 6
Explanation: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.
The total waste is (4-2) + (4-3) + (8-5) = 6.

Example 2:

Input: packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
Output: -1
Explanation: There is no box that the package of size 5 can fit in.

Example 3:

Input: packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
Output: 9
Explanation: It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.
The total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.

 

Constraints:

  • n == packages.length
  • m == boxes.length
  • 1 <= n <= 105
  • 1 <= m <= 105
  • 1 <= packages[i] <= 105
  • 1 <= boxes[j].length <= 105
  • 1 <= boxes[j][k] <= 105
  • sum(boxes[j].length) <= 105
  • The elements in boxes[j] are distinct.

Approach Overview

Problem Overview: You are given package sizes and multiple suppliers offering different box sizes. Each package must go into a box whose size is greater than or equal to the package. For a chosen supplier, every box size can be used multiple times. The goal is to pick a single supplier that packs all packages while minimizing total wasted space (box size minus package size).

Approach 1: Greedy with Sorting and Binary Search (O((n + m) log n), Space: O(n))

Sort the packages array first. Precompute prefix sums so you can quickly calculate the total size of any range of packages. For each supplier, sort their box sizes and skip the supplier if their largest box cannot fit the largest package. Then iterate through each box size and use binary search to find how many remaining packages can fit into that box size (using an upper bound). The wasted space for that batch equals box_size * count - sum(packages_in_range), which you compute using the prefix sums. Accumulate the waste across all box sizes for the supplier and keep the minimum. Sorting and binary searching over the package list keeps the solution efficient. This approach relies heavily on sorting, binary search, and prefix sums to avoid repeatedly scanning the package list.

Approach 2: Two-Pointer Technique with Prefix Sums (O(n log n + m log m), Space: O(n))

After sorting the packages and computing prefix sums, also sort each supplier's box sizes. Instead of running a binary search for every box, maintain a pointer over the package array. As you iterate through increasing box sizes, move the package pointer forward while the package fits in the current box. This effectively groups packages that will use the same box size. Use prefix sums to compute the total package size for the group and calculate waste in constant time. The two-pointer pattern eliminates repeated binary searches and keeps the traversal linear after sorting. The algorithm still checks every supplier and selects the minimum waste among valid ones.

Recommended for interviews: The greedy strategy with sorted packages and binary search is the approach most interviewers expect. It shows you recognize the monotonic structure created by sorting and know how to combine prefix sums with range queries. The two-pointer variant is a solid optimization and demonstrates deeper control over iteration patterns, but the core insight remains the same: process packages in sorted order and batch them into the smallest feasible box sizes.

Approach 1: Greedy Approach with Sorting and Binary Search

To solve this problem, we can follow a greedy strategy which involves sorting the packages and using binary search to fit each package into the smallest possible box. The steps are:

  • Sort the packages to ensure that smaller packages are placed first, which can help minimize wasted space.
  • For each supplier, sort the array of available box sizes.
  • Attempt to fit packages into boxes from each sorted supplier. For each package, use binary search to find the smallest box that can fit the package.
  • Calculate the total wasted space for each supplier and choose the supplier with the minimum wasted space.
  • If any package cannot be fitted into a box for a supplier, mark that supplier as unsuitable.

The final answer is the minimum of the total wastage values for all suitable suppliers, if possible, otherwise return -1.

In this implementation, we sort the packages and use the `bisect_left` method from Python's `bisect` module to find the range of packages that can fit within a given box size. We calculate the waste for each supplier and track the minimum waste globally.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n log n + m * b log b), where n is the number of packages, m is the number of suppliers, and b is the maximum number of box sizes for a supplier which is log b for binary searching over the package list.

Space Complexity: O(1) for additional space used in variables.

Try this approach in the editor →

Approach 2: Two-Pointer Technique and Prefix Sums

This approach leverages a two-pointer technique combined with prefix sums to efficiently calculate the wasted space. The steps are:

  • Sort the packages and calculate the prefix sum for direct package size sums.
  • For each supplier, we sort their box sizes.
  • Use a two-pointer technique where one pointer iterates over the package list and another checks the valid boxes for the current package size.
  • As we determine which packages can fit into a current box size, we calculate the waste using prefix sums rather than recalculating the sum repeatedly.
  • Keep track of the minimum waste for all suppliers.

The answer is either the minimum waste across all suppliers or -1 if any package can't be placed.

The Java solution uses a similar algorithm. For each supplier, determine the total wasted space using the two-pointer method and update the minimum waste accordingly. The prefix sum is implicitly handled by summing package sizes and comparing with the current box size.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(n log n + m * b log b), where n is the number of packages, and m is the number of suppliers.

Space Complexity: O(1) for auxiliary usage.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Sorting and Binary Search

Time Complexity: O(n log n + m * b log b), where n is the number of packages, m is the number of suppliers, and b is the maximum number of box sizes for a supplier which is log b for binary searching over the package list.

Space Complexity: O(1) for additional space used in variables.

Two-Pointer Technique and Prefix Sums

Time Complexity: O(n log n + m * b log b), where n is the number of packages, and m is the number of suppliers.

Space Complexity: O(1) for auxiliary usage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Sorting and Binary SearchO((n + m) log n)O(n)General solution. Easy to reason about using sorted packages and binary search ranges.
Two-Pointer Technique with Prefix SumsO(n log n + m log m)O(n)When you want to avoid repeated binary searches and process packages in a single forward pass.

Video Solution

LeetCode 1889. Minimum Space Wasted From Packaging • Happy Coding • 1,526 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimum Space Wasted From Packaging easy or hard?
Minimum Space Wasted From Packaging is classified as a Hard problem on LeetCode. The difficulty comes from combining multiple techniques: sorting, greedy batching, prefix sums, and binary search across multiple suppliers.
Minimum Space Wasted From Packaging Python/Java solution
Python implementations typically use bisect for binary search along with prefix sums for fast calculations. Java and C++ solutions follow the same logic using Arrays.sort and upper_bound or manual binary search. The algorithmic idea remains identical across languages.
How to solve Minimum Space Wasted From Packaging in O(n)?
A strictly O(n) solution is not feasible because sorting the packages is required to group them efficiently. However, after sorting, you can process packages using a two-pointer technique so each package is visited once per supplier. Prefix sums allow constant-time waste calculation for each group.
What is the best approach for Minimum Space Wasted From Packaging?
The most effective approach sorts the packages and uses a greedy strategy with binary search and prefix sums. For each supplier, you sort their box sizes and determine how many packages fit in each box using an upper-bound search. Prefix sums allow constant-time range sum calculations to compute wasted space efficiently. The overall complexity is roughly O((n + m) log n).
Is Minimum Space Wasted From Packaging asked at Google/Amazon/Meta?
This problem appears in the hard category and reflects patterns commonly used in interviews at companies like Google, Amazon, and Meta. The question tests greedy reasoning, efficient range queries, and combining sorting with binary search.
What data structure is used in Minimum Space Wasted From Packaging?
The solution primarily uses arrays along with prefix sums for fast range sum queries. Binary search is applied on the sorted package array, and sorting is used to maintain monotonic order between package sizes and box sizes.
What is the time complexity of Minimum Space Wasted From Packaging?
The typical optimized solution runs in O((n + m) log n) time, where n is the number of packages and m is the total number of box sizes across suppliers. Sorting the packages costs O(n log n), and each box size uses a binary search over the package array. Space complexity is O(n) due to prefix sums.

Ready to solve this problem?

Practice Minimum Space Wasted From Packaging with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays