Put Boxes Into the Warehouse I Python Solution

Tested Python solution for LeetCode 1564 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 1564, Medium. Topics: Greedy, Array, Sorting. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 22 parametrized pytest cases, and a playground notebook:

lcpy gen -n 1564   # by problem number
lcpy gen -s put_boxes_into_the_warehouse_i   # by problem name

​

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 i^th 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 <em>the maximum number of boxes you can put into the warehouse.</em>

​

Examples

Input: boxes = [4,3,4,1], warehouse = [5,3,3,4,1]
Output: 3
Explanation:
![Explanation 1](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.

Input: boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
Output: 3
Explanation:
![Explanation 2](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.

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

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(m + n log n), Space: O(n) for effective heights
    def max_boxes_in_warehouse(self, boxes: list[int], warehouse: list[int]) -> int:
        # A box of height b can occupy room i iff b <= min(warehouse[0..i]):
        # it must survive every room on the way and fit in room i itself.
        lowest: list[int] = []
        reachable = warehouse[0]
        for height in warehouse:
            reachable = min(reachable, height)
            lowest.append(reachable)

        # Smallest box pairs with the smallest usable (rightmost) room.
        placed = 0
        room = len(lowest) - 1
        for box in sorted(boxes):
            while room >= 0 and lowest[room] < box:
                room -= 1
            if room < 0:
                break
            placed += 1
            room -= 1
        return placed

​

Complexity

Time	Space
O(m + n log n), Space: O(n) for effective heights	-

​

Tags

NeetCode All.