Put Boxes Into the Warehouse I

Put Boxes Into the Warehouse I

What is this problem about?

The Put Boxes Into the Warehouse I problem gives you boxes and warehouse rooms, both represented by their heights. Boxes can only be pushed from one end (left) and must fit under the room height at each position. Find the maximum number of boxes you can push into the warehouse. This coding problem uses a greedy approach after sorting. The array, sorting, and greedy interview pattern is the core.

Why is this asked in interviews?

Pinterest and Google ask this because it tests greedy sorting with a monotone height constraint. The key insight is to sort boxes in descending order and precompute the "effective ceiling" of each room (the minimum height seen so far from the left), then greedily fit the largest boxes first.

Algorithmic pattern used

Sort + precompute effective ceiling + greedy matching. Sort boxes descending. Compute minHeight[i] = min of warehouse[0..i] (effective height limit at position i). Sort effective ceilings descending as well. Greedily match each box to the first room it fits (two-pointer approach).

Example explanation

boxes=[5,3,1], warehouse=[3,4,1,2]. Effective ceilings: [3,3,1,1] (min prefix). Sort boxes desc: [5,3,1]. Sort ceilings desc: [3,3,1,1].

• Box 5: ceiling 3? 5>3 ✗. Next ceiling 3? ✗. Skip box 5.
• Box 3: ceiling 3? 3≤3 ✓. Place. Move to next ceiling.
• Box 1: ceiling 3? 1≤3 ✓. Place. Total = 2 boxes placed.

Common mistakes candidates make

• Not precomputing the effective ceiling (min prefix height) for each room.
• Sorting in ascending order instead of descending.
• Not using a two-pointer for matching boxes to rooms.
• Counting warehouse room count without applying the prefix min constraint.

Interview preparation tip

Warehouse packing problems use the "effective constraint" precomputation: the actual usable height at position i is min(heights[0..i]). This transforms a 2D matching problem into a 1D greedy. Practice similar "fit items into containers with monotone constraints" problems. The descending sort + greedy match pattern generalizes to interval scheduling, bin packing, and capacity planning problems.