You are given two arrays of positive integers, boxes and warehouse, representing the heights of some boxes of unit width and the heights of n rooms in a warehouse respectively. The warehouse's rooms are labelled from 0 to n - 1 from left to right where warehouse[i] (0-indexed) is the height of the ith room.
Boxes are put into the warehouse by the following rules:
Return the maximum number of boxes you can put into the warehouse.
Example 1:
Input: boxes = [4,3,4,1], warehouse = [5,3,3,4,1] Output: 3 Explanation:We can first put the box of height 1 in room 4. Then we can put the box of height 3 in either of the 3 rooms 1, 2, or 3. Lastly, we can put one box of height 4 in room 0. There is no way we can fit all 4 boxes in the warehouse.
Example 2:
Input: boxes = [1,2,2,3,4], warehouse = [3,4,1,2] Output: 3 Explanation:Notice that it's not possible to put the box of height 4 into the warehouse since it cannot pass the first room of height 3. Also, for the last two rooms, 2 and 3, only boxes of height 1 can fit. We can fit 3 boxes maximum as shown above. The yellow box can also be put in room 2 instead. Swapping the orange and green boxes is also valid, or swapping one of them with the red box.
Example 3:
Input: boxes = [1,2,3], warehouse = [1,2,3,4] Output: 1 Explanation: Since the first room in the warehouse is of height 1, we can only put boxes of height 1.
Constraints:
n == warehouse.length1 <= boxes.length, warehouse.length <= 1051 <= boxes[i], warehouse[i] <= 109Problem Overview: You have boxes with different heights and a warehouse represented as rooms with height limits. Boxes can only be pushed from the left entrance. A box stops when it reaches the first room that cannot fit it. The goal is to place the maximum number of boxes inside the warehouse.
Approach 1: Greedy with Prefix Minimum + Sorting (O(n log n) time, O(1) extra space)
The key constraint is movement from left to right. A tall room later in the warehouse may still be unusable if a shorter room appears earlier and blocks larger boxes. Preprocess the warehouse using a prefix minimum so each position i stores the smallest height from 0..i. This represents the actual maximum box height that can reach that room. Next, sort the boxes in ascending order. Iterate through the warehouse from right to left and greedily place the largest remaining box that fits. Filling from the back preserves larger spaces for bigger boxes while smaller boxes naturally fit tighter spaces. Sorting dominates the runtime at O(n log n), while the scan is linear. This approach combines ideas from Greedy, Sorting, and Array processing.
Approach 2: Multiset / Balanced Structure Greedy (O(n log n) time, O(n) space)
Another way is to store all box heights in a balanced structure such as a multiset or priority structure. First compute the same prefix minimum warehouse constraints. Then iterate through rooms from right to left and query the largest box that does not exceed the room height. Remove that box once placed. Each insertion, lookup, and deletion costs O(log n), producing overall O(n log n) time and O(n) space. This version is conceptually straightforward but slower in practice due to extra data structure overhead.
Recommended for interviews: The prefix-minimum + sorting greedy solution is the expected answer. It shows you recognized the hidden constraint that earlier rooms limit later capacity, and that placing boxes from the right maximizes space usage. Explaining the prefix transformation demonstrates strong reasoning about constraints, while the greedy placement proves optimality.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Prefix Minimum + Sorting | O(n log n) | O(1) | Best practical solution. Efficient and simple for interview settings. |
| Greedy with Multiset / Balanced Tree | O(n log n) | O(n) | Useful when dynamically selecting the largest valid box without sorting upfront. |
1564. Put Boxes Into the Warehouse I (LeetCode) • hakunamatasq • 483 views views
Watch 4 more video solutions →Practice Put Boxes Into the Warehouse I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor