LeetCode 1580 - Put Boxes Into the Warehouse II

LeetCode Problem 1580

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

In this problem, we are given 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, meaning each room can contain at most one box.

The important part of the problem is the movement constraint. A box can be inserted from either the left side or the right side of the warehouse. However, while moving inward, if the box encounters a room shorter than the box itself, it cannot move past that room. This means the box stops before the blocking room.

The goal is to maximize the number of boxes that can be successfully placed into the warehouse.

A key observation is that the actual room height is not always the effective usable height. For example, if we push a box from the left, then the minimum height encountered along the path determines whether the box can reach a certain room. Similarly, when pushing from the right, the limiting factor is the minimum height seen from the right side.

The constraints are large:

• Up to 10^5 boxes
• Up to 10^5 warehouse rooms
• Heights can be as large as 10^9

These limits immediately rule out exponential or heavy simulation approaches. We need an algorithm close to O(n log n) or better.

Several edge cases are important:

• The warehouse may contain very small bottleneck rooms that restrict movement.
• There may be more boxes than rooms.
• Very large boxes may never fit anywhere.
• Since insertion is allowed from both sides, a room might be reachable even if one direction is blocked.
• Multiple rooms may effectively have the same usable height after preprocessing.

Approaches

Brute Force Approach

A naive solution would try every possible placement strategy.

One way to think about this is:

1. Try boxes in different orders.
2. For each box, attempt insertion from the left or right.
3. Simulate movement through the warehouse.
4. Mark rooms as occupied.
5. Track the maximum number of successfully inserted boxes.

This brute-force strategy is extremely expensive because:

• There are factorially many box orderings.
• Each insertion may require scanning the warehouse.
• Choosing left versus right doubles branching possibilities.

Even a simplified greedy simulation without preprocessing could still require repeatedly scanning the warehouse for every box, leading to O(n^2) behavior.

With 10^5 elements, such approaches are far too slow.

Key Insight

The core insight is that each warehouse position has an effective capacity determined by accessibility from either side.

For a room i:

• From the left, the tallest box that can reach it is limited by the minimum room height from 0 to i
• From the right, it is limited by the minimum room height from i to n - 1

Since we may insert from either side, the usable height for room i becomes:

max(left_min[i], right_min[i])

This value represents the largest box that can possibly be placed into that room.

Once we compute these effective room capacities, the problem becomes:

Match as many boxes as possible into rooms where box height <= room capacity.

This is now a classic greedy matching problem.

We sort:

• boxes in ascending order
• effective room capacities in ascending order

Then we greedily place the smallest remaining box into the smallest room that can hold it.

This greedy strategy is optimal because using a larger room for a smaller box unnecessarily wastes capacity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential or O(n²)	O(n)	Simulates many insertion orders and placements
Optimal	O(n log n)	O(n)	Uses effective capacities plus greedy matching

Algorithm Walkthrough

1. Compute the left minimum array.

Create an array left_min where:

left_min[i] = minimum warehouse height from 0 to i

This represents the tallest box that can reach room i when entering from the left. 2. Compute the right minimum array.

Create an array right_min where:

right_min[i] = minimum warehouse height from i to n - 1

This represents the tallest box that can reach room i when entering from the right. 3. Compute effective room capacities.

For every room i:

effective[i] = max(left_min[i], right_min[i])

Since boxes may enter from either side, we choose the better accessibility. 4. Sort the boxes.

Sort boxes in ascending order so we place smaller boxes first. 5. Sort the effective room capacities.

Sort the effective capacities in ascending order. 6. Greedily match boxes to rooms.

Use two pointers:

• One for boxes
• One for rooms

If the current box fits into the current room:

• Place it
• Move both pointers forward

Otherwise:

• Move only the room pointer forward to find a larger room

7. Return the number of matched boxes.

Why it works

The preprocessing correctly computes the largest possible box that can reach each room from either side.

After this transformation, the problem reduces to maximizing matches between boxes and room capacities.

Sorting both arrays and greedily matching the smallest possible valid pair is optimal because it preserves larger rooms for larger boxes. This is the standard greedy proof used in interval and assignment matching problems.

Python Solution

from typing import List

class Solution:
    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
        n = len(warehouse)

        left_min = [0] * n
        right_min = [0] * n

        left_min[0] = warehouse[0]
        for i in range(1, n):
            left_min[i] = min(left_min[i - 1], warehouse[i])

        right_min[n - 1] = warehouse[n - 1]
        for i in range(n - 2, -1, -1):
            right_min[i] = min(right_min[i + 1], warehouse[i])

        effective = [
            max(left_min[i], right_min[i])
            for i in range(n)
        ]

        boxes.sort()
        effective.sort()

        box_index = 0
        room_index = 0

        placed = 0

        while box_index < len(boxes) and room_index < n:
            if boxes[box_index] <= effective[room_index]:
                placed += 1
                box_index += 1
                room_index += 1
            else:
                room_index += 1

        return placed

The implementation begins by preprocessing the warehouse from both directions.

left_min[i] tracks the smallest height encountered while moving from the left to room i. Similarly, right_min[i] tracks the smallest height encountered from the right side.

For each room, we compute the maximum of these two values because a box may enter from either direction.

After preprocessing, the warehouse is converted into a list of independent capacities. At that point, the problem becomes a greedy matching problem.

Both arrays are sorted so that smaller boxes are matched first. This prevents wasting large-capacity rooms on tiny boxes.

The two-pointer matching loop efficiently counts the maximum valid placements.

Go Solution

package main

import "sort"

func maxBoxesInWarehouse(boxes []int, warehouse []int) int {
	n := len(warehouse)

	leftMin := make([]int, n)
	rightMin := make([]int, n)

	leftMin[0] = warehouse[0]
	for i := 1; i < n; i++ {
		if leftMin[i-1] < warehouse[i] {
			leftMin[i] = leftMin[i-1]
		} else {
			leftMin[i] = warehouse[i]
		}
	}

	rightMin[n-1] = warehouse[n-1]
	for i := n - 2; i >= 0; i-- {
		if rightMin[i+1] < warehouse[i] {
			rightMin[i] = rightMin[i+1]
		} else {
			rightMin[i] = warehouse[i]
		}
	}

	effective := make([]int, n)

	for i := 0; i < n; i++ {
		if leftMin[i] > rightMin[i] {
			effective[i] = leftMin[i]
		} else {
			effective[i] = rightMin[i]
		}
	}

	sort.Ints(boxes)
	sort.Ints(effective)

	boxIndex := 0
	roomIndex := 0
	placed := 0

	for boxIndex < len(boxes) && roomIndex < n {
		if boxes[boxIndex] <= effective[roomIndex] {
			placed++
			boxIndex++
			roomIndex++
		} else {
			roomIndex++
		}
	}

	return placed
}

The Go implementation mirrors the Python logic closely.

Go does not provide built-in min and max functions for integers, so explicit comparisons are used.

Slices are dynamically sized and behave similarly to Python lists. The algorithm uses sort.Ints for sorting both arrays.

Integer overflow is not a concern because the algorithm only performs comparisons, not arithmetic operations involving large sums or products.

Worked Examples

Example 1

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

Step 1: Compute left minimums

i	warehouse[i]	left_min[i]
0	3	3
1	4	3
2	1	1
3	2	1

Result:

left_min = [3,3,1,1]

Step 2: Compute right minimums

i	warehouse[i]	right_min[i]
3	2	2
2	1	1
1	4	1
0	3	1

Result:

right_min = [1,1,1,2]

Step 3: Compute effective capacities

i	left_min	right_min	effective
0	3	1	3
1	3	1	3
2	1	1	1
3	1	2	2

Result:

effective = [3,3,1,2]

Step 4: Sort arrays

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

Step 5: Greedy matching

Box	Room Capacity	Fits?	Placed
1	1	Yes	1
2	2	Yes	2
2	3	Yes	3
3	3	Yes	4

Final answer:

4

Example 2

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

Step 1: Left minimums

left_min = [2,1,1,1,1]

Step 2: Right minimums

right_min = [1,1,3,4,5]

Step 3: Effective capacities

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

Step 4: Sort arrays

boxes     = [2,3,5,5]
effective = [1,2,3,4,5]

Step 5: Matching

Box	Room Capacity	Fits?	Placed
2	1	No	0
2	2	Yes	1
3	3	Yes	2
5	4	No	2
5	5	Yes	3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + m log m)	Sorting dominates the runtime
Space	O(n)	Extra arrays for preprocessing

Here:

• n = len(warehouse)
• m = len(boxes)

The preprocessing scans the warehouse twice, which costs linear time. The dominant cost comes from sorting the boxes and effective room capacities.

The matching step itself is linear because each pointer only moves forward once.

Test Cases

from typing import List

class Solution:
    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
        n = len(warehouse)

        left_min = [0] * n
        right_min = [0] * n

        left_min[0] = warehouse[0]
        for i in range(1, n):
            left_min[i] = min(left_min[i - 1], warehouse[i])

        right_min[n - 1] = warehouse[n - 1]
        for i in range(n - 2, -1, -1):
            right_min[i] = min(right_min[i + 1], warehouse[i])

        effective = [
            max(left_min[i], right_min[i])
            for i in range(n)
        ]

        boxes.sort()
        effective.sort()

        box_index = 0
        room_index = 0

        placed = 0

        while box_index < len(boxes) and room_index < n:
            if boxes[box_index] <= effective[room_index]:
                placed += 1
                box_index += 1
                room_index += 1
            else:
                room_index += 1

        return placed

sol = Solution()

assert sol.maxBoxesInWarehouse(
    [1,2,2,3,4],
    [3,4,1,2]
) == 4  # Example 1

assert sol.maxBoxesInWarehouse(
    [3,5,5,2],
    [2,1,3,4,5]
) == 3  # Example 2

assert sol.maxBoxesInWarehouse(
    [1,1,1],
    [1,1,1]
) == 3  # All boxes fit exactly

assert sol.maxBoxesInWarehouse(
    [5,6,7],
    [1,2,3]
) == 0  # No box fits

assert sol.maxBoxesInWarehouse(
    [1,2,3],
    [3]
) == 1  # More boxes than rooms

assert sol.maxBoxesInWarehouse(
    [1],
    [10]
) == 1  # Single box fits

assert sol.maxBoxesInWarehouse(
    [10],
    [1]
) == 0  # Single box too large

assert sol.maxBoxesInWarehouse(
    [4,4,4],
    [5,1,5]
) == 2  # Both sides accessible

assert sol.maxBoxesInWarehouse(
    [2,2,2,2],
    [2,2,2]
) == 3  # More boxes than available rooms

assert sol.maxBoxesInWarehouse(
    [1,2,3,4],
    [4,3,2,1]
) == 4  # Descending warehouse heights

Test Summary

Test	Why
Example 1	Validates standard mixed placement
Example 2	Validates bottleneck handling
All values equal	Checks exact-fit behavior
No boxes fit	Ensures algorithm returns zero correctly
More boxes than rooms	Confirms room limit handling
Single fit	Smallest non-trivial success case
Single failure	Smallest non-trivial failure case
Central bottleneck	Verifies two-sided accessibility logic
Too many equal boxes	Confirms greedy matching correctness
Descending warehouse	Tests asymmetric accessibility

Edge Cases

One important edge case occurs when the warehouse contains a very small bottleneck room in the middle. For example:

warehouse = [5,1,5]

A naive approach might incorrectly assume the center room blocks access to both sides entirely. However, since boxes may enter from either side, the outer rooms remain independently usable. The preprocessing with left and right minimum arrays correctly captures this behavior.

Another important case is when there are more boxes than rooms. Since each room can hold only one box, the answer can never exceed the number of warehouse rooms. The greedy matching naturally handles this because matching stops once all rooms are exhausted.

A third tricky case occurs when large boxes appear before small boxes in the input. Without sorting, a greedy strategy might waste large-capacity rooms early and reduce the total number of placements. Sorting ensures smaller boxes are placed first, preserving flexibility for larger boxes later.

A final edge case involves boxes that are too large for every room. In this situation, the matching loop simply skips rooms until exhausted, and the algorithm correctly returns 0 if no valid placement exists.