Problem Description

You have a warehouse with n rooms arranged in a line from left to right, where each room has a specific height given by the array warehouse. You also have multiple boxes with heights given by the array boxes.

The goal is to push as many boxes as possible into the warehouse following these rules:

1. No stacking: Boxes cannot be placed on top of each other - each box occupies one room.

2. Flexible ordering: You can rearrange the boxes in any order before pushing them into the warehouse.

3. Left-to-right only: Boxes must be pushed into the warehouse from the left side and move towards the right.

4. Height constraint: When pushing a box through the warehouse, if it encounters a room with height less than the box's height, the box gets stuck at the room just before it. This also blocks all subsequent boxes from going past this point.

For example, if warehouse = [4, 3, 5, 2, 6] and you push a box of height 4, it can pass through rooms 0 and 1 (heights 4 and 3) but gets stuck before room 3 (height 2), so it ends up in room 2. No other boxes can now be placed beyond room 2.

The solution uses a preprocessing step to find the effective height limit for each room (the minimum height from the entrance to that room), then greedily matches the smallest available boxes to the rightmost available positions in the warehouse. This maximizes the number of boxes that can fit.

Return the maximum number of boxes that can be placed in the warehouse.

Intuition

The key insight is recognizing that a box's journey through the warehouse is limited by the shortest room it encounters along its path. If a box needs to reach room i, it must pass through all rooms from 0 to i-1 first. Therefore, the effective height constraint for placing a box in room i is not just warehouse[i], but the minimum height among all rooms from 0 to i.

This leads us to precompute the "effective height" for each room position. For room i, we calculate left[i] = min(warehouse[0], warehouse[1], ..., warehouse[i]). This represents the maximum height a box can have if we want to place it in room i.

Once we have these effective heights, we need to maximize the number of boxes we can place. Here's where the greedy strategy comes in:

1. Sort boxes in ascending order: We want to use smaller boxes first because they have fewer restrictions and can fit in more places.

2. Fill from right to left: We start placing boxes from the rightmost available position. Why? Because if we can fit a box at position j, we could also fit it at any position k < j (since left[k] >= left[j]). By placing it as far right as possible, we leave more room on the left for other boxes.

3. Match smallest box to rightmost position: For each box (starting from smallest), we find the rightmost room where it can fit. If a box can't fit in the current rightmost available position, we skip that position and try positions further left until we find one that works.

This greedy approach ensures we accommodate as many boxes as possible by always making the locally optimal choice of using the smallest available box for the rightmost available position.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a two-phase approach: preprocessing and greedy matching.

Phase 1: Preprocessing the Warehouse

First, we compute the effective height constraints for each room:

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

• Initialize left array with the first room's height
• For each subsequent room i, calculate left[i] = min(left[i-1], warehouse[i])
• This gives us the minimum height from room 0 to room i, representing the tallest box that can reach room i

For example, if warehouse = [4, 3, 5, 2, 6], then left = [4, 3, 3, 2, 2].

Phase 2: Greedy Box Placement

Next, we sort the boxes and match them with warehouse positions:

boxes.sort()
i, j = 0, n - 1

• Sort boxes in ascending order to prioritize smaller boxes
• Use two pointers: i for boxes (starting from smallest) and j for warehouse positions (starting from rightmost)

The matching loop:

while i < len(boxes):
    while j >= 0 and left[j] < boxes[i]:
        j -= 1
    if j < 0:
        break
    i, j = i + 1, j - 1

• For each box boxes[i], find the rightmost available position where it fits
• If left[j] < boxes[i], the box is too tall for position j, so move j left
• Once we find a valid position (or run out of positions), either:
  • Place the box at position j and move to next box (i + 1) and next available position (j - 1)
  • Or break if no positions remain (j < 0)

The final answer is i, which represents the number of boxes successfully placed.

Time Complexity: O(n + m log m) where n is warehouse length and m is number of boxes Space Complexity: O(n) for the left array

Example Walkthrough

Let's walk through a concrete example with warehouse = [4, 3, 5, 2, 6] and boxes = [3, 5, 5, 2].

Step 1: Preprocess the warehouse

We calculate the effective height constraint for each room by finding the minimum height from the entrance to that room:

• Room 0: left[0] = 4 (only room 0 with height 4)
• Room 1: left[1] = min(4, 3) = 3 (minimum of rooms 0-1)
• Room 2: left[2] = min(3, 5) = 3 (minimum of rooms 0-2)
• Room 3: left[3] = min(3, 2) = 2 (minimum of rooms 0-3)
• Room 4: left[4] = min(2, 6) = 2 (minimum of rooms 0-4)

So left = [4, 3, 3, 2, 2]. This tells us:

• A box needs height ≤ 4 to reach room 0
• A box needs height ≤ 3 to reach room 1
• A box needs height ≤ 3 to reach room 2
• A box needs height ≤ 2 to reach rooms 3 or 4

Step 2: Sort the boxes

Sort boxes = [3, 5, 5, 2] → [2, 3, 5, 5]

Step 3: Greedy matching

Start with i = 0 (smallest box) and j = 4 (rightmost room):

1. Box 0 (height 2): Check room 4 where left[4] = 2. Since 2 ≤ 2, box fits! Place it in room 4. Update: i = 1, j = 3

2. Box 1 (height 3): Check room 3 where left[3] = 2. Since 3 > 2, box doesn't fit. Move left to room 2 where left[2] = 3. Since 3 ≤ 3, box fits! Place it in room 2. Update: i = 2, j = 1

3. Box 2 (height 5): Check room 1 where left[1] = 3. Since 5 > 3, box doesn't fit. Move left to room 0 where left[0] = 4. Since 5 > 4, still doesn't fit. We've run out of rooms (j = -1), so this box cannot be placed.

4. Box 3 (height 5): Since j < 0, no rooms are available. This box cannot be placed.

Result: We successfully placed 2 boxes (the boxes with heights 2 and 3).

The final warehouse configuration would have:

• Room 2: Box of height 3
• Room 4: Box of height 2
• Other rooms: Empty

This demonstrates how the algorithm prioritizes smaller boxes and places them as far right as possible to maximize the total number of boxes that can fit.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m log m) where n is the length of the warehouse array and m is the length of the boxes array.

• Creating the left array requires a single pass through the warehouse array: O(n)
• Sorting the boxes array: O(m log m)
• The while loops for matching boxes to warehouse positions: O(n + m)
  • The outer loop runs at most m times (for each box)
  • The inner loop decrements j from n-1 to potentially -1, but each position is visited at most once across all iterations
  • Combined, both loops together process at most O(n + m) operations

Overall: O(n) + O(m log m) + O(n + m) = O(n + m log m)

Space Complexity: O(n)

• The left array stores n elements: O(n)
• The sorting operation on boxes (if using in-place sorting like Timsort in Python): O(1) to O(m) auxiliary space in worst case, but typically O(log m)
• Other variables (i, j): O(1)

The dominant space usage is the left array, giving us O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Height Constraint Logic

The Problem: A common mistake is thinking that a box can only fit in a room if the box height is less than or equal to that specific room's height, rather than considering all rooms the box must pass through to reach that position.

Incorrect Approach:

# Wrong: Only checking individual room heights
for box in sorted(boxes):
    for i in range(len(warehouse)):
        if warehouse[i] >= box:  # This is wrong!
            # Place box at position i
            break

Why It's Wrong: If warehouse = [4, 3, 5, 2, 6] and we have a box of height 5, the incorrect logic would try to place it at position 2 (height 5). However, the box cannot reach position 2 because it gets stuck at position 1 (height 3).

The Solution: Always use the preprocessed effective_heights array that tracks the minimum height from the entrance to each position:

# Correct: Using effective heights
effective_heights = [warehouse[0]] * n
for i in range(1, n):
    effective_heights[i] = min(effective_heights[i - 1], warehouse[i])

Pitfall 2: Not Starting from the Rightmost Position

The Problem: Another mistake is placing boxes from left to right instead of trying to place them as far right as possible.

Incorrect Approach:

# Wrong: Starting from the left
j = 0  # Starting from leftmost position
for box in sorted(boxes):
    while j < n and effective_heights[j] < box:
        j += 1
    if j < n:
        j += 1  # Move to next position

Why It's Wrong: This approach fills the warehouse from left to right, which can block smaller boxes from reaching deeper positions. For example, with warehouse = [5, 4, 3, 2, 1] and boxes = [1, 2, 3], placing box 1 at position 0 wastes space that could be used for larger boxes.

The Solution: Always start searching from the rightmost position to maximize space utilization:

# Correct: Starting from the right
warehouse_pos = warehouse_length - 1
while warehouse_pos >= 0 and effective_heights[warehouse_pos] < boxes[box_index]:
    warehouse_pos -= 1

Pitfall 3: Forgetting to Sort the Boxes

The Problem: Processing boxes in their original order instead of sorting them first.

Incorrect Approach:

# Wrong: Not sorting boxes
for box in boxes:  # Using original order
    # Try to place box

Why It's Wrong: Without sorting, larger boxes might be placed first and block positions that smaller boxes could have used. For instance, with boxes = [5, 1, 2] and warehouse = [6, 3, 4], placing the box of height 5 first would block all other boxes, resulting in only 1 box placed instead of the optimal 2.

The Solution: Always sort boxes in ascending order before placement:

# Correct: Sort boxes first
boxes.sort()

This ensures smaller boxes are placed first, leaving more room for additional boxes and maximizing the total count.