NeetCode #822LC-1564MediumGreedy
← Back to All Problems#822 · #1564 · Put Boxes Into the Warehouse I(把箱子放进仓库里 I)
📌 Problem Statement & Constraints
You are given
boxes, the heights of unit-width boxes, and warehouse, the heights of rooms in a warehouse. Boxes are pushed in from the left; a box stops if it meets a room shorter than itself, and boxes cannot be stacked. You may reorder the boxes. Return the maximum number of boxes that can be stored. Constraints: 1 <= boxes.length, warehouse.length <= 10^5, 1 <= boxes[i], warehouse[i] <= 10^9.💡 Core Algorithmic Approaches
- A box placed in room
imust pass through rooms0..i, so its height must not exceedmin(warehouse[0..i]). - Replace
warehouse[i]by the prefix minimum, which is non-increasing from left to right. - Sort the boxes ascending and fill the deepest (most constrained) rooms first, using the smallest remaining box that fits.
- This greedy is optimal: a smaller box can always substitute for a larger one, so spending the smallest usable box on the tightest room maximises the count.
💻 Benchmark Python3 Implementation
class Solution:
def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
for i in range(1, len(warehouse)):
warehouse[i] = min(warehouse[i], warehouse[i - 1]) # prefix minimum
boxes.sort()
res = 0
i = 0 # smallest box not yet placed
for j in range(len(warehouse) - 1, -1, -1):
if i < len(boxes) and boxes[i] <= warehouse[j]:
res += 1
i += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(b log b + w): sorting the boxes plus a linear scan of the warehouse.
💾 Space Complexity
O(1) beyond the sort (the warehouse is modified in place).
⚠️ Interview Pitfalls & Follow-ups
- Using suffix minima: boxes enter from the left, so a box in room
imust clear rooms0..i-- the constraint is a prefix minimum, not a suffix minimum. - Scanning rooms left to right: the deepest rooms are the most constrained, so they must be filled first with the smallest boxes.
- Placing the largest box first: that would waste a large box on a tight room; ascending order is required.
- Forgetting that the warehouse array is mutated: reusing it afterwards gives prefix-minimum values, not the original heights.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.