Skip to main content
Talentd

Put Boxes Into the Warehouse II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedySorting8 min readAsked at: Pinterest, Google
Practice this problem

Problem Statement

You are given two arrays of positive integers, boxes and warehouse, representing the heights of some boxes of unit width and the heights of n rooms in a warehouse respectively. The warehouse's rooms are labeled from 0 to n - 1 from left to right where warehouse[i] (0-indexed) is the height of the ith room.

Boxes are put into the warehouse by the following rules:

  • Boxes cannot be stacked.
  • You can rearrange the insertion order of the boxes.
  • Boxes can be pushed into the warehouse from either side (left or right)
  • If the height of some room in the warehouse is less than the height of a box, then that box and all other boxes behind it will be stopped before that room.

Return the maximum number of boxes you can put into the warehouse.

 

Example 1:

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

We can store the boxes in the following order:
1- Put the yellow box in room 2 from either the left or right side.
2- Put the orange box in room 3 from the right side.
3- Put the green box in room 1 from the left side.
4- Put the red box in room 0 from the left side.
Notice that there are other valid ways to put 4 boxes such as swapping the red and green boxes or the red and orange boxes.

Example 2:

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

It is not possible to put the two boxes of height 5 in the warehouse since there's only 1 room of height >= 5.
Other valid solutions are to put the green box in room 2 or to put the orange box first in room 2 before putting the green and red boxes.

 

Constraints:

  • n == warehouse.length
  • 1 <= boxes.length, warehouse.length <= 105
  • 1 <= boxes[i], warehouse[i] <= 109

Approach Overview

Problem Overview: You are given box heights and a warehouse with room height limits. A box can enter the warehouse from either the left or right side but cannot pass through a room with a smaller height. The goal is to place the maximum number of boxes inside the warehouse.

Approach 1: Direct Simulation (Brute Force) (Time: O(n*m), Space: O(1))

A straightforward idea is to try placing each box by scanning the warehouse from both directions and checking where it fits. For every box, iterate from the left entrance until a valid slot is found, and repeat the same from the right entrance. Choose the best available position that has not been occupied. This approach quickly becomes inefficient because every placement may require scanning the entire warehouse. With many boxes and rooms, the repeated scans lead to O(n*m) time.

Approach 2: Preprocessing + Sorting + Greedy (Time: O(n log n), Space: O(n))

The key observation is that a box can only reach a position if every room along the path from the entrance has height greater than or equal to the box height. Compute two arrays: a prefix minimum from the left and a suffix minimum from the right. The prefix value at index i represents the tallest box that can reach that slot from the left; the suffix value represents the same from the right.

For each warehouse slot, take max(prefixMin[i], suffixMin[i]). This represents the largest box that can reach that position from at least one side. Now the problem becomes matching boxes to slots based on capacity.

Sort the boxes array and the computed slot capacities. Then use a greedy strategy: iterate through both arrays and place the smallest remaining box into the smallest slot that can hold it. If the box height is less than or equal to the slot capacity, place it and move both pointers forward. Otherwise skip that slot. Sorting ensures smaller boxes fill tighter spaces while preserving larger slots for bigger boxes.

This approach converts the path restriction problem into a simple capacity matching problem. The preprocessing step captures the warehouse constraints, and the greedy placement maximizes the number of boxes placed.

Recommended for interviews: The preprocessing + sorting greedy solution is what interviewers expect. It demonstrates understanding of constraint propagation, array preprocessing, and greedy matching. Brute force shows the basic idea but does not scale. Practicing similar patterns from Array, Greedy, and Sorting problems helps recognize this optimization quickly.

Solution

First, we preprocess the warehouse to get the maximum height of each room. Then, we sort both the boxes and the warehouse. Starting with the smallest box and the smallest room, if the current room's height is greater than or equal to the current box's height, we can place the current box in the current room; otherwise, we continue to the next room.

Finally, we return the number of boxes that can be placed.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the warehouse.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Simulation (Brute Force)O(n*m)O(1)Small inputs or initial reasoning about how boxes move from both ends
Preprocessing + Sorting + GreedyO(n log n)O(n)General case; optimal interview solution using prefix/suffix constraints and greedy placement

Video Solution

1580. Put Boxes Into the Warehouse II - Week 3/5 Leetcode June Challenge • Programming Live with Larry • 470 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Put Boxes Into the Warehouse II easy or hard?
Put Boxes Into the Warehouse II is classified as Medium difficulty. The challenge comes from recognizing that boxes can enter from both ends and converting the path restriction into a slot capacity problem using prefix and suffix preprocessing.
Put Boxes Into the Warehouse II Python or Java solution
Implement the preprocessing step to compute prefix and suffix minimum arrays, build the slot capacity array, sort both boxes and capacities, then iterate with two pointers to greedily place boxes. The same algorithm works in Python, Java, C++, and Go with O(n log n) complexity.
How to solve Put Boxes Into the Warehouse II in O(n log n)?
First compute prefix minimum heights from the left and suffix minimum heights from the right. For each position take the maximum of these two values to determine the largest box that can reach that slot. Sort the boxes and the slot capacities, then greedily place boxes from smallest to largest while scanning the slots.
What is the best approach for Put Boxes Into the Warehouse II?
The most efficient solution uses preprocessing with prefix and suffix minimum arrays followed by sorting and a greedy placement strategy. Compute the maximum box height that can reach each warehouse slot from either side, sort both boxes and slot capacities, and greedily match them. This runs in O(n log n) time due to sorting and uses O(n) extra space.
What data structure is used in Put Boxes Into the Warehouse II?
The solution primarily uses arrays along with sorting. Prefix and suffix arrays capture reachability constraints, and the sorted arrays enable a greedy two-pointer style placement of boxes into valid warehouse slots.
What is the time complexity of Put Boxes Into the Warehouse II?
The optimal algorithm runs in O(n log n) time. Preprocessing the warehouse with prefix and suffix minimum arrays takes O(n), while sorting the boxes and slot capacities dominates the complexity with O(n log n). The final greedy scan is linear.
Is Put Boxes Into the Warehouse II asked at Google Amazon or Meta?
Problems involving greedy placement, sorting, and constrained array traversal appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of warehouse packing and capacity matching are common because they test preprocessing insights and greedy reasoning.

Ready to solve this problem?

Practice Put Boxes Into the Warehouse II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Put Boxes Into the Warehouse I