LeetCode 1564 - Put Boxes Into the Warehouse I

LeetCode Problem 1564

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem gives us two arrays:

• boxes, where each value represents the height of a box
• warehouse, where each value represents the height of a room in the warehouse

Every box has width 1, and every warehouse room also has width 1. Boxes cannot be stacked, so each room can hold at most one box.

The important restriction is how boxes move through the warehouse. Boxes can only be inserted from the left side and pushed toward the right. If a box encounters a room whose height is smaller than the box height, the box stops before entering that room. Since the box blocks the path, every box behind it also becomes unable to move further.

This means a box placed deep inside the warehouse must be able to pass through every room before it.

The goal is to maximize how many boxes can be placed into the warehouse.

A critical observation is that the effective height of a room is not just its own height. A box must pass through all previous rooms first. Therefore, the usable height at position i is actually:

min(warehouse[0], warehouse[1], ..., warehouse[i])

If any earlier room is shorter, that earlier room becomes the bottleneck for every later room.

The constraints are large:

• Up to 10^5 boxes
• Up to 10^5 warehouse rooms

This immediately tells us that quadratic approaches will be too slow. We need an algorithm close to O(n log n) or better.

Several edge cases are important:

• The first warehouse room may be very small, limiting every room after it.
• There may be more boxes than rooms.
• Many boxes may be too tall to fit anywhere.
• Warehouse heights may decrease sharply, creating bottlenecks.
• The optimal placement may require using smaller boxes first.

Approaches

Brute Force Approach

A straightforward approach is to try every possible placement strategy.

One possible brute-force idea is:

1. For every box, attempt to place it into the deepest possible room.
2. Check whether the box can pass through all earlier rooms.
3. Mark the room as occupied.
4. Repeat for all permutations or greedy choices.

This eventually finds the correct answer because it explores valid placements. However, it is extremely inefficient.

Even a simplified brute-force strategy that scans the warehouse for every box would require repeatedly checking room accessibility and occupancy. With up to 10^5 elements, repeated scans become prohibitively expensive.

The main issue is that naive placement decisions can easily become suboptimal. A large box placed too early may block smaller boxes that could have fit deeper inside.

Key Insight

The key insight is that every warehouse position is limited by the minimum height encountered from the left.

For example:

warehouse = [5, 3, 4, 2]
effective  = [5, 3, 3, 2]

Even though room 2 has height 4, a box taller than 3 can never reach it because room 1 blocks the path.

Once we preprocess the warehouse into these effective heights, the problem becomes much simpler.

We then sort the boxes in ascending order and greedily try to place the smallest boxes into the tightest available warehouse spaces.

Why does this work?

• Small rooms can only accept small boxes.
• Large rooms can accept both small and large boxes.
• Therefore, we should reserve larger rooms for larger boxes whenever possible.

This is a classic greedy matching strategy.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n) to exponential depending on strategy	O(1) to O(m)	Repeated placement checks become too slow
Optimal	O(m log m + n)	O(1) extra, excluding sort	Sort boxes and greedily match to effective warehouse heights

Here, m = len(boxes) and n = len(warehouse).

Algorithm Walkthrough

1. Preprocess the warehouse heights.

Traverse the warehouse from left to right. For each room, replace its height with the minimum height seen so far.

This transforms the warehouse into its effective accessible heights.

Example:

warehouse = [5,3,4,2]
effective = [5,3,3,2]

This step is necessary because a box must pass through all earlier rooms before reaching a later room. 2. Sort the boxes in ascending order.

Smaller boxes are more flexible and can fit into more rooms. Sorting allows us to greedily place boxes into the smallest available spaces first. 3. Start filling the warehouse from right to left.

The rightmost rooms are usually the most restrictive because their effective heights are constrained by all earlier rooms.

We use:

• box_index to track the current smallest unused box
• Iterate through warehouse rooms from right to left

4. For each warehouse room:

• If the current box fits, place it and move to the next box.
• If it does not fit, skip the room because larger boxes also will not fit.

5. Continue until:

• All rooms are processed, or
• All boxes are placed

6. Return the number of placed boxes.

Why it works

The algorithm works because the warehouse constraints create a monotonic structure after preprocessing.

Once the effective heights are computed, placing smaller boxes into tighter spaces is always optimal. If a small room is left unused while a larger room takes a small box, we may later fail to place a larger box. By processing rooms from smallest-accessible positions toward larger ones and always using the smallest fitting box, we maximize the total number of successful placements.

This greedy strategy never wastes large capacity on unnecessarily small boxes.

Python Solution

from typing import List

class Solution:
    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
        # Step 1: preprocess warehouse heights
        for i in range(1, len(warehouse)):
            warehouse[i] = min(warehouse[i], warehouse[i - 1])

        # Step 2: sort boxes
        boxes.sort()

        box_index = 0
        placed_boxes = 0

        # Step 3: fill warehouse from right to left
        for room_index in range(len(warehouse) - 1, -1, -1):
            if box_index < len(boxes) and boxes[box_index] <= warehouse[room_index]:
                placed_boxes += 1
                box_index += 1

        return placed_boxes

The implementation begins by converting the warehouse into its effective heights. Each room becomes the minimum value seen so far from the left. This models the actual accessibility constraint.

Next, the boxes are sorted in ascending order. This allows the algorithm to greedily place the smallest remaining box into each available room.

The algorithm then iterates through the warehouse from right to left. The rightmost rooms are typically the most constrained because their effective heights include all previous bottlenecks.

Whenever the current smallest box fits into the current room, the algorithm places it and advances to the next box. If the box does not fit, the room is skipped because no larger box could fit either.

Finally, the total number of successfully placed boxes is returned.

Go Solution

package main

import "sort"

func maxBoxesInWarehouse(boxes []int, warehouse []int) int {
	// Step 1: preprocess warehouse heights
	for i := 1; i < len(warehouse); i++ {
		if warehouse[i] > warehouse[i-1] {
			warehouse[i] = warehouse[i-1]
		}
	}

	// Step 2: sort boxes
	sort.Ints(boxes)

	boxIndex := 0
	placedBoxes := 0

	// Step 3: fill warehouse from right to left
	for roomIndex := len(warehouse) - 1; roomIndex >= 0; roomIndex-- {
		if boxIndex < len(boxes) && boxes[boxIndex] <= warehouse[roomIndex] {
			placedBoxes++
			boxIndex++
		}
	}

	return placedBoxes
}

The Go implementation follows the same logic as the Python version.

One notable difference is that Go does not provide a built-in min function for integers in older standard library versions, so the preprocessing step uses a manual comparison.

Go slices are used directly, and sorting is performed with sort.Ints.

Since all values are within 10^9, standard Go int values are completely safe from overflow concerns.

Worked Examples

Example 1

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

Step 1: Preprocess Warehouse

Index	Original	Effective
0	5	5
1	3	3
2	3	3
3	4	3
4	1	1

Effective warehouse:

[5,3,3,3,1]

Step 2: Sort Boxes

[1,3,4,4]

Step 3: Fill From Right to Left

Room Index	Room Height	Current Box	Fits?	Boxes Placed
4	1	1	Yes	1
3	3	3	Yes	2
2	3	4	No	2
1	3	4	No	2
0	5	4	Yes	3

Final answer:

3

Example 2

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

Step 1: Preprocess Warehouse

Index	Original	Effective
0	3	3
1	4	3
2	1	1
3	2	1

Effective warehouse:

[3,3,1,1]

Step 2: Sort Boxes

[1,2,2,3,4]

Step 3: Fill From Right to Left

Room Index	Room Height	Current Box	Fits?	Boxes Placed
3	1	1	Yes	1
2	1	2	No	1
1	3	2	Yes	2
0	3	2	Yes	3

Final answer:

3

Example 3

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

Step 1: Preprocess Warehouse

Effective warehouse:

[1,1,1,1]

Step 2: Sort Boxes

[1,2,3]

Step 3: Fill From Right to Left

Room Index	Room Height	Current Box	Fits?	Boxes Placed
3	1	1	Yes	1
2	1	2	No	1
1	1	2	No	1
0	1	2	No	1

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m log m + n)	Sorting boxes dominates the runtime
Space	O(1) extra	Sorting aside, only a few variables are used

The preprocessing step scans the warehouse once, which costs O(n).

Sorting the boxes costs O(m log m).

The final greedy placement scan processes the warehouse once more in O(n) time.

No additional data structures proportional to input size are created, so the algorithm uses constant extra space aside from sorting overhead.

Test Cases

from typing import List

class Solution:
    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
        for i in range(1, len(warehouse)):
            warehouse[i] = min(warehouse[i], warehouse[i - 1])

        boxes.sort()

        box_index = 0
        placed = 0

        for i in range(len(warehouse) - 1, -1, -1):
            if box_index < len(boxes) and boxes[box_index] <= warehouse[i]:
                placed += 1
                box_index += 1

        return placed

solution = Solution()

assert solution.maxBoxesInWarehouse([4,3,4,1], [5,3,3,4,1]) == 3  # example 1
assert solution.maxBoxesInWarehouse([1,2,2,3,4], [3,4,1,2]) == 3  # example 2
assert solution.maxBoxesInWarehouse([1,2,3], [1,2,3,4]) == 1  # example 3

assert solution.maxBoxesInWarehouse([1], [1]) == 1  # single box fits
assert solution.maxBoxesInWarehouse([2], [1]) == 0  # single box too large

assert solution.maxBoxesInWarehouse([1,1,1], [1,1,1]) == 3  # all equal
assert solution.maxBoxesInWarehouse([5,6,7], [1,2,3]) == 0  # no boxes fit

assert solution.maxBoxesInWarehouse([1,2,3], [3,3,3]) == 3  # all boxes fit
assert solution.maxBoxesInWarehouse([4,4,4], [5,5]) == 2  # more boxes than rooms

assert solution.maxBoxesInWarehouse([2,2,2], [5,1,5,5]) == 1  # bottleneck blocks later rooms
assert solution.maxBoxesInWarehouse([1,2,2,2], [2,2,2,2]) == 4  # exact capacity match

assert solution.maxBoxesInWarehouse([10,1,1,1], [2,2,2,2]) == 3  # one oversized box
assert solution.maxBoxesInWarehouse([3,5,5,2], [6,5,4,3]) == 3  # decreasing warehouse heights

print("All test cases passed!")

Test	Why
[4,3,4,1], [5,3,3,4,1]	Validates the first official example
[1,2,2,3,4], [3,4,1,2]	Validates bottleneck behavior
[1,2,3], [1,2,3,4]	Shows first room restricting all later rooms
[1], [1]	Smallest valid fitting case
[2], [1]	Smallest non-fitting case
[1,1,1], [1,1,1]	All identical values
[5,6,7], [1,2,3]	No box can fit
[1,2,3], [3,3,3]	Every box fits successfully
[4,4,4], [5,5]	More boxes than available rooms
[2,2,2], [5,1,5,5]	Internal bottleneck reduces future capacity
[1,2,2,2], [2,2,2,2]	Exact matching capacities
[10,1,1,1], [2,2,2,2]	Oversized box must be ignored
[3,5,5,2], [6,5,4,3]	Mixed heights and decreasing constraints

Edge Cases

One important edge case occurs when the first warehouse room is very small. Since every box must pass through the first room, that room becomes a bottleneck for the entire warehouse. For example:

warehouse = [1, 100, 100, 100]

Even though later rooms are large, only boxes of height 1 can enter the warehouse at all. The preprocessing step correctly transforms the warehouse into:

[1,1,1,1]

which ensures the algorithm handles this restriction properly.

Another important edge case occurs when there are more boxes than rooms. Since each room can contain only one box, the answer can never exceed the number of rooms. The greedy algorithm naturally handles this because it iterates through rooms exactly once and places at most one box per room.

A third tricky case involves oversized boxes mixed with smaller ones. Consider:

boxes = [100,1,1]
warehouse = [2,2,2]

A naive strategy might waste time trying to place the oversized box first. By sorting boxes in ascending order, the algorithm prioritizes smaller boxes that can actually fit, maximizing the total number placed.

Another subtle edge case happens when warehouse heights fluctuate upward after a small room:

warehouse = [5,2,6,7]

Even though later rooms appear large, the room with height 2 blocks access. The preprocessing step converts this into:

[5,2,2,2]

which correctly models the true reachable capacity of every room.