Put Boxes Into the Warehouse I - Video Solutions
Google Interview Question - Put Boxes Into the Warehouse I- Leetcode 1564- Python
Put Boxes Into the Warehouse I - Video Solution
Watch 5 video solutions for Put Boxes Into the Warehouse I, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Sephorus has 522 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- Boxes cannot be stacked.
- You can rearrange the insertion order of the boxes.
- Boxes can only be pushed into the warehouse from left to right only.
- If the height of some room in the warehouse is less than the height of a box, then that box and all other boxes behind it will be stopped before that room.
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] <= 109
Approach Overview
Problem 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.
Complexity Analysis
| 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. |