Put Boxes Into the Warehouse I
Asked at Pinterest
Problem
Put Boxes Into the Warehouse I gives you box heights and warehouse room heights (rooms in a line, entered from the left). A box can pass into a room only if it fits under every room before it. How many boxes can you store? Normalize the rooms to their effective heights, then fill from the far end with the smallest boxes.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Pinterest questions → |
How to Think About It
A room behind a low room is effectively only as tall as the lowest room before it. Replace each room height with the prefix minimum: eff[i] = min(warehouse[0..i]).
Now effective heights are non-increasing from left to right. The deepest rooms are the most restrictive, so fill them first with the smallest boxes.
Key insight: sort boxes ascending. Walk rooms from the last to the first; if the smallest remaining box fits the current room, place it and move to the next box. Otherwise leave the room empty and move left.
Why greedy works: a small box can go anywhere a big one can, so using small boxes on tight rooms never blocks a better arrangement.
Walkthrough: boxes [4,3,4,1], warehouse [5,3,3,4,1]. Effective [5,3,3,3,1]. Sorted boxes [1,3,4,4]. Room 4 (1) takes 1, room 3 (3) takes 3, rooms 2 and 1 (3) cannot take 4, room 0 (5) takes 4 -> 3 boxes.
Optimal Approach
Step 1: Convert warehouse to prefix minimums.
Step 2: Sort boxes ascending; i = 0.
Step 3: For each room from right to left: if i < len(boxes) and boxes[i] <= room: i += 1.
Step 4: Return i.
Time: O(n log n + m). Space: O(1) extra (in-place prefix minimum).
What Trips People Up in Real Interviews
Ignoring the entrance constraint and matching raw room heights. A tall room behind a short one cannot receive a tall box.
Filling from the entrance with the largest boxes, which can waste deep rooms.
Trying to place the largest boxes first in the deepest rooms — the deepest rooms are the tightest.
Forgetting that each room holds at most one box.
Solution Code
def maxBoxesInWarehouse(boxes, warehouse):
for i in range(1, len(warehouse)):
warehouse[i] = min(warehouse[i], warehouse[i - 1])
boxes.sort()
i = 0
for room in reversed(warehouse):
if i < len(boxes) and boxes[i] <= room:
i += 1
return iFrequently Asked Questions
What is the Put Boxes Into the Warehouse I problem?
Put Boxes Into the Warehouse I gives you box heights and warehouse room heights (rooms in a line, entered from the left). A box can pass into a room only if it fits under every room before it. How many boxes can you store? Normalize the rooms to their effective heights, then fill from the far end with the smallest boxes.
How do you solve Put Boxes Into the Warehouse I?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Put Boxes Into the Warehouse I?
Put Boxes Into the Warehouse I is asked at Pinterest. It is a medium difficulty problem.
What are common mistakes on Put Boxes Into the Warehouse I?
- Ignoring the entrance constraint and matching raw room heights. A tall room behind a short one cannot receive a tall box.
- Filling from the entrance with the largest boxes, which can waste deep rooms.
- Trying to place the largest boxes first in the deepest rooms — the deepest rooms are the tightest.
- Forgetting that each room holds at most one box.