Photo by Elevate on Unsplash

Put Boxes Into the Warehouse I — Daily Challenge May

Today’s question is from Daily Leetcode Coding Challenge — May Edition. It is a medium-tagged question. Let us look into the problem statement.

1564. Put Boxes Into the Warehouse I

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 labeled 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.

Example

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

Understanding the problem:

Since we can only push boxes in the warehouse from left to right, the height of the box that can be pushed to a room is dependent on the previous room’s height. For example, if we have rooms of height 4, 7 respectively, we can’t place a box of height 5 into the room of height seven since it cant fit in a preceding room of height 4. So one thing is clear we can only place a box in a room if all preceding room’s minimum height accommodates the said box.

Approach:

As mentioned above the actual height that can be considered at any room is the minimum of preceding heights. So we update the height of the rooms with the minimum of preceding rooms.

E.g. [5,3,3,4,1] → [5, 3, 3, 3, 1]

Once we have the effective height we start to fit the boxes, with bigger boxes first. For each room in the warehouse, we try to find if we can fit the box in that room. We do this in a greedy fashion. To do that we sort the boxes in descending order.

Code Implementation:

def maxBoxesInWarehouse(boxes, warehouse):
    for i in range(1, len(warehouse)):
        warehouse[i]= min(warehouse[i], warehouse[i-1])
    boxes.sort(reverse=True)
    j = 0
    res = 0
    for height in warehouse:
        while j < len(boxes) and boxes[j] > height: 
            j += 1
        if j >= len(boxes):
            break
        res += 1
        j += 1
    return res

Complexity Analysis:

• Time complexity: O(n*log(n)) for sorting the boxes m for creating the min-height array. O(n + m) for finding the box for the room.
• Constant space

Happy coding!!