1564 - Put Boxes Into the Warehouse I

Difficulty: Medium | Pattern: Greedy + Sorting | Company tags: Google

Problem Statement

You are given two arrays of positive integers, boxes and warehouse, representing the heights of boxes and rooms in a warehouse, respectively. The warehouse's rooms are labelled from 0 to n-1 from left to right, where warehouse[i] is the height of i-th room.

Boxes are put into the warehouse one box at a time, from left to right. A box may be placed in room i if:

1. The box is not taller than warehouse[i]
2. The box is not taller than any room from 0 to i-1 (you must pass through all previous rooms)

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

Example 2:

Input: boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
Output: 3

Approach: Greedy — O(n log n + m log m)

Key insight:

1. Precompute effective heights: since boxes must pass through all rooms, the effective height of room i is min(warehouse[0..i]).
2. Sort boxes descending. Greedily fit the largest box possible into each room (from left to right by effective height).

def maxBoxesInWarehouse(boxes: list[int], warehouse: list[int]) -> int:
    # Compute effective heights (running min from left)
    n = len(warehouse)
    effective = warehouse[:]
    for i in range(1, n):
        effective[i] = min(effective[i], effective[i-1])
    
    # Sort boxes descending to try largest first
    boxes.sort(reverse=True)
    
    count = 0
    box_idx = 0
    
    for h in effective:
        if box_idx >= len(boxes):
            break
        if boxes[box_idx] <= h:
            count += 1
            box_idx += 1
    
    return count

Algorithm Flow

Dry Run

boxes=[4,3,4,1], warehouse=[5,3,3,4,1]

Effective heights: [5, min(5,3)=3, min(3,3)=3, min(3,4)=3, min(3,1)=1] Sorted boxes (desc): [4,4,3,1]

effective	largest unused box	fits?	count
5	4	4 lte 5 ✓	1
3	4	4 gt 3 ✗ skip	1
3	3	3 lte 3 ✓	2
3	1	1 lte 3 ✓	3
1	(no more boxes)	—	3

3 ✓

Complexity

• Time: O(n log n + m log m) for sorting + O(n + m) for greedy pass
• Space: O(n) for effective heights

Key Terms

Term	Definition
Effective height	The tightest bottleneck a box must pass through to reach room i, computed as the running minimum of warehouse[0..i].
Greedy algorithm	Strategy that makes the locally optimal choice at each step (fit the largest feasible box) without backtracking.
Monotonic prefix minimum	A running minimum computed left to right, used here to model the "must pass through all previous rooms" constraint.
Two-pointer matching	Advancing through sorted boxes and sorted/processed rooms simultaneously to match largest-fits-first.

FAQ

Q: Why sort boxes in descending order rather than ascending? A: Rooms are processed left to right in their natural (unsorted) effective-height order, so a greedy match works best when we always try the largest remaining box first — placing big boxes early leaves smaller boxes free for tighter rooms later.

Q: Why do we need the "effective height" prefix minimum instead of using warehouse[i] directly? A: A box entering room i must have already passed through every room from 0 to i-1, so its size is capped by the smallest room encountered along the way, not just the height of room i itself.

Q: What if boxes is empty or warehouse is empty? A: The greedy loop either never finds a box to place or never has a room to check, so count naturally stays 0 — no special-case handling required.

Q: How does this differ from "Put Boxes Into the Warehouse II" (LeetCode 1580)? A: In version II, boxes can enter from either end of the warehouse, so the effective height must be computed as the minimum from both directions (prefix min from the left AND suffix min from the right) before the same greedy matching applies.

Q: Can boxes be reordered before insertion? A: Yes — the problem allows sorting boxes freely since only the multiset of box heights matters, not their original order; only warehouse order is fixed because it reflects physical room layout.

Quick Revision

• Rooms have a physical layout; a box entering room i must fit through every room 0..i-1 first.
• Compute effective[i] = min(warehouse[0..i]) — a running minimum from the left.
• Sort boxes descending to try the largest box first.
• Walk effective left to right; if the largest remaining box fits, place it and advance to the next box.
• If it doesn't fit, skip that room and keep the box in reserve for a room with a smaller effective height further along.
• Count increments only on a successful placement.
• Time: O(n log n + m log m) for sorting, O(n + m) for the greedy scan.
• Space: O(n) for the effective-height array.
• Core pattern: reduce a constrained placement problem to two sorted sequences matched greedily.

Related Problems

• 1580 - Put Boxes Into the Warehouse II — same idea but boxes can enter from either side, requiring a two-directional running minimum.
• 455 - Assign Cookies — classic greedy two-pointer matching of sorted needs to sorted capacities.
• Related pattern: greedy matching between two sorted arrays (e.g., "Boats to Save People", "Advantage Shuffle") generally follows this fit-largest-first-or-smallest-first template.