Problem statement

https://leetcode.com/problems/put-boxes-into-the-warehouse-ii/

Solution

This problem is similar to 1564, but here we can choice to use both ends. So, let us first again trasform our W in such way that we can use full heights. For each point we can either try to reach from the left or from the right. We need to evaluate cumulative minimums from both sides and then choose maximums. In the end we have something like 7 -> 5 -> 2 -> 3 -> 3 -> 5 -> 6. This technique is very similar to problem 42. Trapping Rain Water

Now, notice that problem becomes basically the same as 1564: we start with smallest box and try to put it to smallest room. For each next box we need to put in in the smallest room avaliable: does not matter from which side.

Complexity

It is O(n log n + m log m) for time - we sort W as well. It can be improved to O(n + m log m) if we use the fact that it is almost sorted. Space is O(m + n).

Code

class Solution:
    def maxBoxesInWarehouse(self, B, W):
        left = list(accumulate(W, min))
        right = list(accumulate(W[::-1], min))[::-1]
        W = sorted([max(x, y) for x, y in zip(left, right)])[::-1]
        B = sorted(B)[::-1]
        
        ans = 0
        i, j = len(W) - 1, len(B) - 1
        while i >= 0 and j >= 0:
            if W[i] >= B[j]:
                ans += 1
                j = j - 1
            i -= 1
                
        return ans