Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1500-1599/1564.Put%20Boxes%20Into%20the%20Warehouse%20I/images/11.png)
Input: boxes = [4,3,4,1], warehouse = [5,3,3,4,1]
Output: 3
Explanation: 
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1500-1599/1564.Put%20Boxes%20Into%20the%20Warehouse%20I/images/12.png)
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:

1
2
3
4
5
6
7
8
9

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1500-1599/1564.Put%20Boxes%20Into%20the%20Warehouse%20I/images/21.png)
Input: boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
Output: 3
Explanation: 
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1500-1599/1564.Put%20Boxes%20Into%20the%20Warehouse%20I/images/22.png)
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:

1
2
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 <= 10^5
  • 1 <= boxes[i], warehouse[i] <= 10^9

Solution

Method 1 – Greedy with Prefix Min

Intuition

Since boxes can only be pushed from left to right, each room’s effective height is limited by the smallest room to its left. We can precompute the minimum height up to each room, then greedily fit the smallest boxes into the tightest spaces.

Approach

  1. Sort the boxes in ascending order.
  2. For the warehouse, compute a prefix minimum array so that each room’s height is the minimum of itself and all rooms to its left.
  3. Use a pointer to iterate through the warehouse from left to right, and try to fit the smallest available box into each room.
  4. If the box fits, move to the next box; otherwise, try the next room.
  5. Return the total number of boxes placed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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 i = 0, j = 0, ans = 0;
        while (i < boxes.size() && j < n) {
            if (boxes[i] <= warehouse[j]) { ++ans; ++i; }
            ++j;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func maxBoxesInWarehouse(boxes []int, warehouse []int) int {
    sort.Ints(boxes)
    for i := 1; i < len(warehouse); i++ {
        if warehouse[i] > warehouse[i-1] {
            warehouse[i] = warehouse[i-1]
        }
    }
    i, j, ans := 0, 0, 0
    for i < len(boxes) && j < len(warehouse) {
        if boxes[i] <= warehouse[j] {
            ans++; i++
        }
        j++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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 i = 0, j = 0, ans = 0;
        while (i < boxes.length && j < warehouse.length) {
            if (boxes[i] <= warehouse[j]) { ans++; i++; }
            j++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun maxBoxesInWarehouse(boxes: IntArray, warehouse: IntArray): Int {
        boxes.sort()
        for (i in 1 until warehouse.size) {
            warehouse[i] = minOf(warehouse[i], warehouse[i-1])
        }
        var i = 0; var j = 0; var ans = 0
        while (i < boxes.size && j < warehouse.size) {
            if (boxes[i] <= warehouse[j]) { ans++; i++ }
            j++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from typing import List
class Solution:
    def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
        boxes.sort()
        for i in range(1, len(warehouse)):
            warehouse[i] = min(warehouse[i], warehouse[i-1])
        i = j = ans = 0
        while i < len(boxes) and j < len(warehouse):
            if boxes[i] <= warehouse[j]:
                ans += 1
                i += 1
            j += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn max_boxes_in_warehouse(mut boxes: Vec<i32>, mut warehouse: Vec<i32>) -> i32 {
        boxes.sort();
        for i in 1..warehouse.len() {
            warehouse[i] = warehouse[i].min(warehouse[i-1]);
        }
        let (mut i, mut j, mut ans) = (0, 0, 0);
        while i < boxes.len() && j < warehouse.len() {
            if boxes[i] <= warehouse[j] { ans += 1; i += 1; }
            j += 1;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    maxBoxesInWarehouse(boxes: number[], warehouse: number[]): number {
        boxes.sort((a, b) => a - b);
        for (let i = 1; i < warehouse.length; ++i)
            warehouse[i] = Math.min(warehouse[i], warehouse[i-1]);
        let i = 0, j = 0, ans = 0;
        while (i < boxes.length && j < warehouse.length) {
            if (boxes[i] <= warehouse[j]) { ans++; i++; }
            j++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(N log N + M), where N is the number of boxes and M is the number of warehouse rooms. Sorting boxes is O(N log N), and the prefix min and scan are O(M).
  • 🧺 Space complexity: O(1), ignoring the space for sorting.