1580. Put Boxes Into the Warehouse II

MediumGreedyArraySorting
Leetcode Link

Problem Description

You've got several boxes and a warehouse with a series of rooms in it. Each box has a height, and each room in the warehouse has a height as well. Your job is to figure out the maximum number of these boxes that can fit into the warehouse based on the following set of rules:

  • You can't stack the boxes on top of each other; each must sit on the warehouse floor.
  • You are allowed to reorder the boxes before you start placing them in the warehouse.
  • Boxes can be pushed into the warehouse from either end (left or right side).
  • If a box is too tall for a particular room in the warehouse, it, and any boxes behind it, can't proceed further. They are effectively stopped at that point.

The challenge is to maximize the number of boxes that can fit into the warehouse given these constraints.

Intuition

To solve this problem, take a look at both the boxes and the warehouse room heights. Since the boxes can be reorganized, sort them from smallest to tallest, which allows you to begin with filling from the smallest box and move up. For the warehouse rooms, consider that a box can come from either side. You should find the effective height for each room in the warehouse, which is the maximum height that a box can be to pass through that room from either side.

To do this, create two arrays, left and right:

  • left[i] gives the minimum height of the rooms on the left of room i, including i itself.
  • right[i] gives the minimum height of the rooms on the right of room i, including i itself.

After knowing the minimum of the left and right for each room, calculate the effective height for each room by taking the maximum of the minimums. Then sort the warehouse room heights to likewise place smaller effective heights first.

Finally, place boxes in the warehouse by checking:

  • Start placing the smallest box.
  • Increment the number of boxes placed (ans) each time a box fits the room height.
  • If you encounter a warehouse room that is shorter than the current box, skip to the next room until you find a room tall enough or run out of rooms.
  • Keep going until all boxes are checked or there is no more room with sufficient height for the remaining boxes.

This approach will give you the maximum number of boxes that can fit into the warehouse.

Learn more about Greedy and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search can be used to find whether two components in a graph are connected.

Solution Approach

The implementation is quite straightforward if you follow the intuition behind the solution. Let's break down the steps of the algorithm used, referring to the Python code snippet provided:

  1. Initialization: Two arrays left and right are initialized to record the minimum height so far from the left and the right respectively. These arrays help us determine the effective height of a warehouse room. Additionally, the variable n stores the length of the warehouse.

  2. Populate the left and right arrays:

    • For left, start from the second room (index 1) and move to the last, for each room storing the minimum height of all rooms encountered before, including the current one.
    • For right, start from the second to last room (index n - 2) and move towards the first room (index 0), with the same principle as the left.
    • In this context, inf is used to initialize left[0] and right[-1] so these values don't restrict any room height.

  3. Calculate the effective heights: Iterate through the warehouse array and calculate the effective height for each room. This is the minimum height that a box can be to pass through that room from either direction.

  4. Sort both boxes and warehouse: Boxes are sorted in non-decreasing order, so you always attempt to place the smallest boxes first, which increases the likelihood of accommodating more boxes. The warehouse is sorted because we've converted the warehouse into a set of potential box heights, from smallest to largest effective height.

  5. Place boxes into the warehouse: The algorithm then iterates through the boxes array and tries to place each box into the sorted warehouse:

    • Use a pointer i which starts at 0, representing the effective height to insert into the warehouse.
    • If the current box is taller than the warehouse[i], increment i to find an appropriate height.
    • If a suitable room is found, increase the number of placed boxes ans by 1 and move to the next box.

  6. Return the result: Once all possible boxes are placed, or there’s no more room in the warehouse, the loop ends, and ans gives the number of boxes placed. Return ans.

By undertaking these steps, the algorithm ensures that we are optimizing the number of boxes placed in the warehouse by strategically choosing dimensions and placements.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example Walkthrough

Let's illustrate the solution approach with a small example.

Suppose we have the following boxes and warehouse room heights:

Boxes: [3, 4, 1, 2]
Warehouse rooms: [5, 3, 4, 1]

First, we sort the array of boxes in non-decreasing order: [1, 2, 3, 4].

For the warehouse rooms, we need to find the effective height for each room. First, we initialize two arrays, left and right, and then populate them:

  • Initialize left and right: left = [inf, -1, -1, -1], right = [-1, -1, -1, inf]
  • Populating left: We compare each room's height to the minimum of all previous rooms, starting from the left. So left becomes [5, 3, 3, 1].
  • Populating right: Similarly, we compare each room's height to the minimum of all previous rooms, starting from the right. So right becomes [1, 1, 3, 5].

Now, we calculate the effective height for each room by determining the maximum height that a box can pass through from either end. We take the maximum of the minimums from left and right for each room:

Effective heights: [5, 3, 3, 5]
(Note that we take the maximum between left[i] and right[i] for each room.)

We then sort the effective heights for the rooms to facilitate the insertion of boxes: [3, 3, 5, 5].

Now we are ready to place the boxes into the effective heights of the warehouse:

  • Start with the smallest box (1). It fits in the first room which has an effective height of 3.
  • Move to the second box (2). It also fits in the next room with an effective height of 3.
  • Then the third box (3) fits in the next room with an effective height of 5.
  • Lastly, the fourth box (4) fits in the final room with an effective height of 5.

Since all boxes can be placed into the warehouse, our answer (ans) is 4.

Thus, using this approach, we have placed all four boxes into the warehouse effectively.

Solution Implementation

1class Solution:
2    def max_boxes_in_warehouse(self, boxes: List[int], warehouse: List[int]) -> int:
3        # Find the length of the warehouse
4        warehouse_length = len(warehouse)
5      
6        # Initialize the left and right limits, which are used to track 
7        # the minimum height of the left and right side at each position
8        left_min = [0] * warehouse_length
9        right_min = [0] * warehouse_length
10      
11        # Set the first element of left limits and the last element of right limits 
12        # to infinity as the starting point
13        left_min[0] = right_min[-1] = float('inf')
14      
15        # Calculate the left_min for each position in the warehouse
16        for i in range(1, warehouse_length):
17            left_min[i] = min(left_min[i - 1], warehouse[i - 1])
18      
19        # Calculate the right_min for each position in the warehouse
20        for i in range(warehouse_length - 2, -1, -1):
21            right_min[i] = min(right_min[i + 1], warehouse[i + 1])
22      
23        # Update each position in the warehouse to be the minimum height restriction considering 
24        # the limitations from both sides
25        for i in range(warehouse_length):
26            warehouse[i] = min(warehouse[i], max(left_min[i], right_min[i]))
27      
28        # Sort the boxes and warehouse to prepare for the greedy approach
29        boxes.sort()
30        warehouse.sort()
31      
32        # Initialize the answer and pointer i for the warehouse array
33        box_count = i = 0
34      
35        # Iterate over each box to see if it fits in the warehouse
36        for box in boxes:
37            # Find a space in the warehouse where the current box can fit
38            while i < warehouse_length and warehouse[i] < box:
39                i += 1
40            if i == warehouse_length:
41                # If we reached the end of the warehouse, no more boxes can fit
42                break
43            # If a box is placed in the warehouse, increase the count
44            box_count += 1
45          
46            # Move to the next position for the following box
47            i += 1
48      
49        # Return the total number of boxes that can be placed in the warehouse
50        return box_count
51
1import java.util.Arrays;
2
3class Solution {
4    // Maximum number of boxes that can be placed in the warehouse
5    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
6        int warehouseSize = warehouse.length;
7        int[] minLeftHeight = new int[warehouseSize]; // Minimum height to the left
8        int[] minRightHeight = new int[warehouseSize]; // Minimum height to the right
9        final int infinity = Integer.MAX_VALUE;
10        minLeftHeight[0] = infinity;
11        minRightHeight[warehouseSize - 1] = infinity;
12
13        // Populate the minimum height from left to right
14        for (int i = 1; i < warehouseSize; ++i) {
15            minLeftHeight[i] = Math.min(minLeftHeight[i - 1], warehouse[i - 1]);
16        }
17
18        // Populate the minimum height from right to left
19        for (int i = warehouseSize - 2; i >= 0; --i) {
20            minRightHeight[i] = Math.min(minRightHeight[i + 1], warehouse[i + 1]);
21        }
22
23        // Update warehouse heights to the minimum height at each position
24        for (int i = 0; i < warehouseSize; ++i) {
25            warehouse[i] = Math.min(warehouse[i], Math.max(minLeftHeight[i], minRightHeight[i]));
26        }
27
28        // Sort both the box sizes and the warehouse aisle heights
29        Arrays.sort(boxes);
30        Arrays.sort(warehouse);
31
32        int maxBoxes = 0; // Maximum boxes that can be placed
33        int warehouseIndex = 0; // Pointer to navigate through warehouse heights
34      
35        // Loop through each box to find its place in the warehouse
36        for (int box : boxes) {
37            // Find a position in the warehouse where the box can fit
38            while (warehouseIndex < warehouseSize && warehouse[warehouseIndex] < box) {
39                warehouseIndex++;
40            }
41            // If there are no more positions left, break out of the loop
42            if (warehouseIndex == warehouseSize) {
43                break;
44            }
45            // Place the box in the warehouse and move to the next position
46            maxBoxes++;
47            warehouseIndex++;
48        }
49        return maxBoxes; // Return the maximum number of boxes that can be placed
50    }
51}
52
1class Solution {
2public:
3    int maxBoxesInWarehouse(vector<int>& boxes, vector<int>& warehouse) {
4        // Get the size of the warehouse
5        int warehouseSize = warehouse.size();
6        // Define an infinity value used for comparisons
7        const int INF = 1 << 30;
8
9        // These vectors will hold the minimum height limitation when looking from the left and right
10        vector<int> minLeft(warehouseSize, INF);
11        vector<int> minRight(warehouseSize, INF);
12
13        // Fill the minLeft vector with the minimum height limitation so far from the left
14        for (int i = 1; i < warehouseSize; ++i) {
15            minLeft[i] = min(minLeft[i - 1], warehouse[i - 1]);
16        }
17
18        // Fill the minRight vector with the minimum height limitation so far from the right
19        for (int i = warehouseSize - 2; i >= 0; --i) {
20            minRight[i] = min(minRight[i + 1], warehouse[i + 1]);
21        }
22
23        // Update the warehouse's limitations with the stricter of the minLeft and minRight at each position
24        for (int i = 0; i < warehouseSize; ++i) {
25            warehouse[i] = min(warehouse[i], max(minLeft[i], minRight[i]));
26        }
27
28        // Sort the array of boxes and the modified warehouse array
29        sort(boxes.begin(), boxes.end());
30        sort(warehouse.begin(), warehouse.end());
31
32        // Initialize the count of boxes that can be put into the warehouse
33        int boxCount = 0;
34        // Index for the warehouse's position
35        int warehouseIndex = 0;
36
37        // Iterate through each box
38        for (int box : boxes) {
39            // Increment the warehouseIndex until a position is found where the box fits
40            while (warehouseIndex < warehouseSize && warehouse[warehouseIndex] < box) {
41                warehouseIndex++;
42            }
43            // If we've reached the end of the warehouse, we can't fit any more boxes
44            if (warehouseIndex == warehouseSize) {
45                break;
46            }
47            // Successfully placed the box, increment count and move to next warehouse position
48            boxCount++;
49            warehouseIndex++;
50        }
51        // Return the total count of boxes that can be put into the warehouse
52        return boxCount;
53    }
54};
55
1function maxBoxesInWarehouse(boxes: number[], warehouse: number[]): number {
2    // Get the size of the warehouse
3    let warehouseSize: number = warehouse.length;
4
5    // Define an infinity value used for comparisons
6    const INF: number = 1 << 30;
7
8    // These arrays will hold the minimum height limitation when looking from the left and right
9    let minLeft: number[] = new Array(warehouseSize).fill(INF);
10    let minRight: number[] = new Array(warehouseSize).fill(INF);
11
12    // Fill the minLeft with the minimum height limitation so far from the left
13    for (let i = 1; i < warehouseSize; ++i) {
14        minLeft[i] = Math.min(minLeft[i - 1], warehouse[i - 1]);
15    }
16
17    // Fill the minRight with the minimum height limitation so far from the right
18    for (let i = warehouseSize - 2; i >= 0; --i) {
19        minRight[i] = Math.min(minRight[i + 1], warehouse[i + 1]);
20    }
21
22    // Update the warehouse's limitations with the stricter of the minLeft and minRight at each position
23    for (let i = 0; i < warehouseSize; ++i) {
24        warehouse[i] = Math.min(warehouse[i], Math.max(minLeft[i], minRight[i]));
25    }
26
27    // Sort the array of boxes and the modified warehouse array
28    boxes.sort((a, b) => a - b);
29    warehouse.sort((a, b) => a - b);
30
31    // Initialize the count of boxes that can be put into the warehouse
32    let boxCount: number = 0;
33    // Index for the warehouse's position
34    let warehouseIndex: number = 0;
35
36    // Iterate through each box
37    for (const box of boxes) {
38        // Increment the warehouseIndex until a position is found where the box fits
39        while (warehouseIndex < warehouseSize && warehouse[warehouseIndex] < box) {
40            warehouseIndex++;
41        }
42        // If we've reached the end of the warehouse, we can't fit any more boxes
43        if (warehouseIndex === warehouseSize) {
44            break;
45        }
46        // Successfully placed the box, increment count, and move to the next warehouse position
47        boxCount++;
48        warehouseIndex++;
49    }
50
51    // Return the total count of boxes that can be put into the warehouse
52    return boxCount;
53}
54
Not Sure What to Study? Take the 2-min Quiz：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be broken down into the following parts:

  1. Initializing the left and right arrays with 0 and inf respectively, and the subsequent loop for populating left takes O(n) time, where n is the number of positions in the warehouse.

  2. The second loop for populating right also takes O(n) time.

  3. The third loop where the warehouse heights are updated by taking the minimum of warehouse height, left, and right at each position requires O(n) time.

  4. Sorting the boxes array is O(m log m), where m is the number of boxes.

  5. Sorting the modified warehouse array takes O(n log n) time.

  6. The final loop, which matches boxes to positions in the warehouse, will in the worst case iterate through all the boxes and all positions, which takes O(m + n) time.

Adding up all these parts, the time complexity is O(n) + O(n) + O(n) + O(m log m) + O(n log n) + O(m + n).

Since sorting operations have the highest complexity, the overall time complexity is dominated by them: O(m log m) + O(n log n). In the case where n and m are similar in magnitude, this can be simplified to O(n log n).

Space Complexity

The space complexity is determined by the extra space used in the algorithm apart from the input, which are:

  1. The space used by the left array, which is O(n).

  2. The space used by the right array, also O(n).

  3. There is constant space used for variables like ans and i, which we represent as O(1).

So, the total extra space used by the algorithm is O(n) + O(n) which simplifies to O(n).

In conclusion, the time complexity of the code is O(m log m) + O(n log n) and the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following problems can be solved with backtracking (select multiple)

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫