Skip to main content
Talentd

Put Boxes Into the Warehouse I - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedySorting5 min readAsked at: Amazon, 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 labelled 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 only be pushed into the warehouse from left to right only.
  • 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 = [4,3,4,1], warehouse = [5,3,3,4,1]
Output: 3
Explanation: 

We can first put the box of height 1 in room 4. Then we can put the box of height 3 in either of the 3 rooms 1, 2, or 3. Lastly, we can put one box of height 4 in room 0.
There is no way we can fit all 4 boxes in the warehouse.

Example 2:

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

Notice that it's not possible to put the box of height 4 into the warehouse since it cannot pass the first room of height 3.
Also, for the last two rooms, 2 and 3, only boxes of height 1 can fit.
We can fit 3 boxes maximum as shown above. The yellow box can also be put in room 2 instead.
Swapping the orange and green boxes is also valid, or swapping one of them with the red box.

Example 3:

Input: boxes = [1,2,3], warehouse = [1,2,3,4]
Output: 1
Explanation: Since the first room in the warehouse is of height 1, we can only put boxes of height 1.

 

Constraints:

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

Approach Overview

Problem Overview: You have boxes with different heights and a warehouse represented as rooms with height limits. Boxes can only be pushed from the left entrance. A box stops when it reaches the first room that cannot fit it. The goal is to place the maximum number of boxes inside the warehouse.

Approach 1: Greedy with Prefix Minimum + Sorting (O(n log n) time, O(1) extra space)

The key constraint is movement from left to right. A tall room later in the warehouse may still be unusable if a shorter room appears earlier and blocks larger boxes. Preprocess the warehouse using a prefix minimum so each position i stores the smallest height from 0..i. This represents the actual maximum box height that can reach that room. Next, sort the boxes in ascending order. Iterate through the warehouse from right to left and greedily place the largest remaining box that fits. Filling from the back preserves larger spaces for bigger boxes while smaller boxes naturally fit tighter spaces. Sorting dominates the runtime at O(n log n), while the scan is linear. This approach combines ideas from Greedy, Sorting, and Array processing.

Approach 2: Multiset / Balanced Structure Greedy (O(n log n) time, O(n) space)

Another way is to store all box heights in a balanced structure such as a multiset or priority structure. First compute the same prefix minimum warehouse constraints. Then iterate through rooms from right to left and query the largest box that does not exceed the room height. Remove that box once placed. Each insertion, lookup, and deletion costs O(log n), producing overall O(n log n) time and O(n) space. This version is conceptually straightforward but slower in practice due to extra data structure overhead.

Recommended for interviews: The prefix-minimum + sorting greedy solution is the expected answer. It shows you recognized the hidden constraint that earlier rooms limit later capacity, and that placing boxes from the right maximizes space usage. Explaining the prefix transformation demonstrates strong reasoning about constraints, while the greedy placement proves optimality.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Prefix Minimum + SortingO(n log n)O(1)Best practical solution. Efficient and simple for interview settings.
Greedy with Multiset / Balanced TreeO(n log n)O(n)Useful when dynamically selecting the largest valid box without sorting upfront.

Video Solution

Google Interview Question - Put Boxes Into the Warehouse I- Leetcode 1564- Python • Sephorus • 522 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Put Boxes Into the Warehouse I easy or hard?
Put Boxes Into the Warehouse I is rated Medium on LeetCode. The challenge is recognizing that earlier warehouse rooms limit access to later ones, which requires a prefix minimum preprocessing step before applying a greedy placement strategy.
Put Boxes Into the Warehouse I Python/Java solution
Implement the greedy approach: compute prefix minimums for the warehouse array, sort the boxes, and iterate from the end of the warehouse placing the largest box that fits. The same logic works across Python, Java, C++, Go, and TypeScript with O(n log n) complexity.
How to solve Put Boxes Into the Warehouse I in O(n log n)?
First convert the warehouse heights into prefix minimum values so each position reflects the smallest room height before it. Sort the boxes by height. Traverse the warehouse from right to left and greedily place the largest remaining box that fits each room. This combination of sorting and a linear scan gives O(n log n) time.
What is the best approach for Put Boxes Into the Warehouse I?
The optimal solution uses a greedy strategy with a prefix minimum transformation of the warehouse array. Compute the minimum height reachable at each position, sort the boxes, and place them from the rightmost warehouse room to the left. This ensures larger boxes get the largest available spaces. The time complexity is O(n log n) due to sorting.
Is Put Boxes Into the Warehouse I asked at Google/Amazon/Meta?
Greedy placement and array constraint problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. Variants involving packing, scheduling, or constrained placement are common because they test reasoning about greedy choices and edge cases.
What data structure is used in Put Boxes Into the Warehouse I?
The main solution uses arrays with a prefix minimum transformation and sorting. Some alternative implementations use a multiset or priority structure to dynamically select the largest box that fits a room, but sorting with a greedy scan is more common.
What is the time complexity of Put Boxes Into the Warehouse I?
The optimal algorithm runs in O(n log n) time. Sorting the boxes takes O(n log n), and scanning the warehouse to place boxes takes O(n). The space complexity can be O(1) extra if the warehouse array is modified in place for prefix minimums.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Put Boxes Into the Warehouse II