We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Put Boxes Into the Warehouse II

Number: 1719

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

We are given a set of boxes – each with a given height – and a warehouse consisting of a row of rooms (each room has its own height). Boxes are “pushed” into the warehouse from either the left end or the right end. When inserting from one side the boxes must fill rooms contiguously and in the order of the entrance – if a box is “too tall” for a room (or the effective (restricted) height of that room from previous insertions) then not only does that box stop but no boxes behind it (from that entrance) can continue further. We are allowed to decide the order in which boxes are inserted. The task is to determine the maximum number of boxes that can be put into the warehouse when you are allowed to push from either the left or the right side.

For example, in one case the warehouse rooms are [3,4,1,2] and boxes are [1,2,2,3,4]. One valid way is to use one side to “fill” a contiguous set of rooms and the other side to fill the remaining rooms – overall placing 4 boxes. (The second example shows that some boxes might “never” be placed because too few rooms have a high ceiling.)

Key Insights

  • Only a contiguous prefix (from the left) and a contiguous suffix (from the right) of the warehouse can actually be filled.
  • Because the boxes may be re‐ordered arbitrarily, it is always best to “reserve” the smallest possible boxes for rooms with lower effective height.
  • One can “simulate” the process by pre‐sorting boxes (in descending order) and then “assigning” each box to one of the two ends. The idea is that at any moment the “door” (either left or right) has the unmodified room–height (the next room that has not yet been filled) and one should use the door with the larger entrance (because it is more “forgiving”) if the box fits.
  • When a box can be placed through one door, that door “moves” (i.e. the next room along that side becomes the candidate); once the left and right door cross, there are no more rooms.
  • This greedy strategy (when coded carefully) uses two pointers (one for left and one for right) iterating along the warehouse.

Space and Time Complexity

Time Complexity: O(m log m + n)

  • Sorting the boxes takes O(m log m) where m is the number of boxes.
  • The single pass “assignment” uses at most O(m+n) steps. Space Complexity: O(m)
  • We store a sorted copy of the boxes.

Solution

We first sort the boxes in descending order so that we consider larger boxes before smaller ones. We then keep two pointers: one (leftIdx) for the leftmost room that is still available (starting at index 0) and one (rightIdx) for the rightmost available room (starting at warehouse.length-1). For each box (from largest to smallest) we try to “push” it from the side with the larger door height. (This is because a room with a higher ceiling can ‘admit’ a larger box while leaving the less “generous” side for a box that must be very small.) If the box fits through that door (i.e. its height is ≤ the room’s height) we place it and move the corresponding pointer inward. If it does not fit the chosen side, we check the other door. We continue until there are no more boxes or when the two pointers cross (i.e. no more available rooms). This method produces the maximum count of boxes placed.

A small “gotcha” is that even though a box might sit in either door, choosing the door with the higher entrance (if available) is a safe greedy decision since it “saves” the scarce high–ceiling room on the other side for a box that might need it. This reasoning can be formalized by an exchange argument.

Code Solutions

Below are code solutions in Python, JavaScript, C++ and Java. Each solution includes line‐by‐line comments.

# Python solution

def maxBoxesInWarehouse(boxes, warehouse):
    # Sort boxes in descending order.
    boxes.sort(reverse=True)
    
    left_idx = 0               # pointer for the leftmost (available) room
    right_idx = len(warehouse) - 1   # pointer for the rightmost (available) room
    count = 0                  # count boxes placed
    
    # Process each box from largest to smallest.
    for box in boxes:
        # If no room remains, break out.
        if left_idx > right_idx:
            break
        
        # Decide which door to try first:
        # We pick the door with the greater current room height.
        if warehouse[left_idx] >= warehouse[right_idx]:
            # Try left door first.
            if box <= warehouse[left_idx]:
                count += 1
                left_idx += 1  # move to the next room from the left
            # Else, try right door as a backup.
            elif box <= warehouse[right_idx]:
                count += 1
                right_idx -= 1  # move to the next room from the right
        else:
            # Right door has larger height.
            if box <= warehouse[right_idx]:
                count += 1
                right_idx -= 1
            elif box <= warehouse[left_idx]:
                count += 1
                left_idx += 1
                
    return count

# Example usage:
boxes = [1,2,2,3,4]
warehouse = [3,4,1,2]
print(maxBoxesInWarehouse(boxes, warehouse))  # Expected output: 4
← Back to All Questions