Problem Description

You are given two integer arrays: boxes and warehouse.

• boxes[i] represents the height of the ith box.
• warehouse[j] represents the height of the jth room in the warehouse (from left to right).

Thought Process

At first glance, the problem seems to suggest a brute-force approach: try every possible way to assign boxes to rooms. However, with potentially large input sizes, this would be computationally expensive and inefficient.

The key insight is that since boxes must be placed in the leftmost available room that can fit them, and each room can hold only one box, the order of placement matters. We should try to fit the smallest boxes into the smallest rooms that can accommodate them, maximizing the number of boxes we can place.

Another realization is that the effective height of each room is constrained by the minimum height encountered so far (from left to right), because a tall room blocked by a short one before it cannot be accessed by a tall box. Thus, we need to preprocess the warehouse array to reflect these constraints.

Solution Approach

Here's how we can solve the problem efficiently:

1. Preprocess the warehouse:
   • For each room, compute the minimum height up to that room (from the left).
   • This ensures that no room is considered taller than any room before it, reflecting the actual accessible height for each position.
2. Sort the boxes:
   • Sort the boxes array in ascending order. This helps us fit the smallest boxes first, which gives us more flexibility for larger boxes later.
3. Greedy placement:
   • Start from the rightmost room in the warehouse and try to fit the largest remaining box that can fit into that room.
   • Move backwards through the warehouse, and forwards through the sorted boxes, placing boxes whenever they fit.

Example Walkthrough

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

Step 1: Preprocess warehouse
Compute minimum height up to each room:
- warehouse[0] = 5
- warehouse[1] = min(5, 3) = 3
- warehouse[2] = min(3, 3) = 3
- warehouse[3] = min(3, 4) = 3
- warehouse[4] = min(3, 1) = 1
So, processed warehouse: [5, 3, 3, 3, 1]

Step 2: Sort boxes
Sorted boxes: [1, 3, 4, 4]

Step 3: Place boxes
Start from the rightmost room (warehouse[4] = 1):
- Box 1 fits (box[0] = 1), place it.
Next room (warehouse[3] = 3):
- Box 3 fits (box[1] = 3), place it.
Next room (warehouse[2] = 3):
- Box 4 doesn't fit (box[2] = 4), skip.
Next room (warehouse[1] = 3):
- Box 4 doesn't fit, skip.
Next room (warehouse[0] = 5):
- Box 4 fits (box[2] = 4), place it.

Result: 3 boxes can be placed.

Time and Space Complexity

Brute-force approach:
- Would involve trying every permutation of boxes and placements, leading to O(n!) time complexity (where n is the number of boxes), which is infeasible for large n.

Optimized approach (described above):

• Sorting the boxes: O(n log n), where n is the number of boxes.
• Preprocessing the warehouse: O(m), where m is the number of rooms.
• Greedy placement (two pointers): O(max(n, m)).

Summary

The problem is elegantly solved by combining sorting, preprocessing, and a greedy two-pointer strategy. By reducing each room's effective height to the minimum seen so far, and by matching the smallest available boxes to the tightest fitting rooms, we maximize the number of boxes placed. This approach is both efficient and intuitive, and it avoids the combinatorial explosion of brute-force methods.

Code Implementation

class Solution:
    def maxBoxesInWarehouse(self, boxes, warehouse):
        boxes.sort()
        # Preprocess warehouse: min height up to each position
        for i in range(1, len(warehouse)):
            warehouse[i] = min(warehouse[i], warehouse[i-1])
        res = 0
        i = len(boxes) - 1
        # Start from rightmost room
        for j in range(len(warehouse)-1, -1, -1):
            if i >= 0 and boxes[i] <= warehouse[j]:
                res += 1
                i -= 1
        return res
      

class Solution {
public:
    int maxBoxesInWarehouse(vector<int>& boxes, vector<int>& warehouse) {
        sort(boxes.begin(), boxes.end());
        int n = warehouse.size();
        for (int i = 1; i < n; ++i) {
            warehouse[i] = min(warehouse[i], warehouse[i-1]);
        }
        int res = 0;
        int i = boxes.size() - 1;
        for (int j = n - 1; j >= 0; --j) {
            if (i >= 0 && boxes[i] <= warehouse[j]) {
                ++res;
                --i;
            }
        }
        return res;
    }
};
      

import java.util.Arrays;
class Solution {
    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
        Arrays.sort(boxes);
        for (int i = 1; i < warehouse.length; i++) {
            warehouse[i] = Math.min(warehouse[i], warehouse[i - 1]);
        }
        int res = 0;
        int i = boxes.length - 1;
        for (int j = warehouse.length - 1; j >= 0; j--) {
            if (i >= 0 && boxes[i] <= warehouse[j]) {
                res++;
                i--;
            }
        }
        return res;
    }
}
      

var maxBoxesInWarehouse = function(boxes, warehouse) {
    boxes.sort((a, b) => a - b);
    for (let i = 1; i < warehouse.length; i++) {
        warehouse[i] = Math.min(warehouse[i], warehouse[i-1]);
    }
    let res = 0;
    let i = boxes.length - 1;
    for (let j = warehouse.length - 1; j >= 0; j--) {
        if (i >= 0 && boxes[i] <= warehouse[j]) {
            res++;
            i--;
        }
    }
    return res;
};