⚡Flashcard Drill➔
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

  1. A box placed in room i must pass through rooms 0..i, so its height must not exceed min(warehouse[0..i]).
  2. Replace warehouse[i] by the prefix minimum, which is non-increasing from left to right.
  3. Sort the boxes ascending and fill the deepest (most constrained) rooms first, using the smallest remaining box that fits.
  4. 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 i must clear rooms 0..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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems