Put Boxes Into the Warehouse II

Put Boxes Into the Warehouse II

What is this problem about?

Put Boxes Into the Warehouse II extends Part I by allowing boxes to be pushed from either end (left or right). This flexibility means two-directional insertion, requiring a two-pointer approach to maximize box placement. The array, sorting, and greedy interview pattern is the core.

Why is this asked in interviews?

Pinterest and Google ask this as the harder variant, testing whether candidates can adapt the one-directional greedy to a bidirectional approach. The two-pointer technique simultaneously considers best-fit from both ends.

Algorithmic pattern used

Sort + two-pointer greedy. Sort boxes descending. Precompute effective ceilings from both left and right (prefix min and suffix min). Use two pointers lo (leftmost room) and hi (rightmost room). For each box from largest to smallest: try fitting into the higher of the two current room ceilings. If it fits either, place it and advance that pointer.

Example explanation

boxes=[5,3,2,1], warehouse=[4,1,3,2]. Left ceilings: [4,1,1,1]. Right ceilings: [1,1,2,2]. Two pointers lo=0(left ceiling=4), hi=3(right ceiling=2).

• Box 5: max(4,2)=4. 5>4 ✗. Skip.
• Box 3: max(4,2)=4. 3≤4 ✓. Place in lo. lo=1(left ceiling=1).
• Box 2: max(1,2)=2. 2≤2 ✓. Place in hi. hi=2(right ceiling=2).
• Box 1: max(1,2)=2. 1≤2 ✓. Place. Total = 3 boxes.

Common mistakes candidates make

• Applying the two-pointer without precomputing ceilings from both sides.
• Sorting boxes ascending (must be descending to greedily fit largest first).
• Advancing wrong pointer after placement.
• Not handling the case where a box fits neither end.

Interview preparation tip

Part II teaches bidirectional greedy: always use the "best available slot" from either end. The descending sort ensures you fit the hardest-to-place boxes first. Practice similar bidirectional problems: "two-pointer string matching," "merge from both ends." This pattern appears in scheduling and assignment problems where flexibility in placement order matters.