Put Boxes Into the Warehouse II - Practice Coding Problems

Put Boxes Into the Warehouse II - 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 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 be pushed into the warehouse from either side (left or right)
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.

Input & Output

Example 1 — Basic Case

$ Input: boxes = [4,3,4,1], warehouse = [5,3,3,4,1]

› Output: 3

💡 Note: We can place 3 boxes: box with height 1 can go anywhere, boxes with height 3 can fit in positions with height ≥3, and one box with height 4 can fit in position with height ≥4. From left: effective heights are [5,3,3,3,1]. From right: effective heights are [1,1,1,1,1]. Optimal placement yields 3 boxes.

Example 2 — Single Room

$ Input: boxes = [1,2,2,3,4], warehouse = [3]

› Output: 1

💡 Note: Only one room available with height 3. We can place at most 1 box (any box with height ≤3). The optimal choice is to place one of the boxes with height 1, 2, or 3.

Example 3 — No Fit

$ Input: boxes = [5,5,5], warehouse = [2,1,1]

› Output: 0

💡 Note: All boxes have height 5, but all warehouse rooms have height less than 5. No boxes can be placed.

Constraints

1 ≤ boxes.length ≤ 10⁵
1 ≤ warehouse.length ≤ 10⁵
1 ≤ boxes[i], warehouse[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Boxes [4,3,4,1] and Warehouse [5,3,3,4,1]

Process

Calculate effective heights and match with sorted boxes

Output

Maximum 3 boxes can be placed

Key Takeaway

🎯 Key Insight: Calculate effective heights from both directions and use greedy placement with sorted boxes for optimal results

Asked in

a Amazon 25 G Google 18 M Microsoft 12

The key insight is calculating effective heights from both directions and using a greedy two-pointer approach. Best approach is Greedy Two Pointers with sorted boxes. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Two Pointers	O(n log n)	O(n)	Sort boxes and greedily match with effective warehouse heights from both ends
Brute Force	O(n! × 2^n × n)	O(n)	Try all possible combinations of box arrangements from both sides

Greedy Two Pointers — Algorithm Steps

Calculate effective heights from left and right
Sort boxes in ascending order
Use two pointers to place boxes greedily
Choose the side that maximizes placements

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Effective Heights

Find minimum heights reachable from each direction

Sort Boxes

Process boxes from smallest to largest

Greedy Placement

Place each box on the side with better opportunity

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int* boxes, int boxesSize, int* warehouse, int warehouseSize) {
    int n = warehouseSize;
    
    // Calculate effective heights from left
    int* leftHeights = (int*)malloc(n * sizeof(int));
    leftHeights[0] = warehouse[0];
    for (int i = 1; i < n; i++) {
        leftHeights[i] = min(leftHeights[i-1], warehouse[i]);
    }
    
    // Calculate effective heights from right
    int* rightHeights = (int*)malloc(n * sizeof(int));
    rightHeights[n-1] = warehouse[n-1];
    for (int i = n-2; i >= 0; i--) {
        rightHeights[i] = min(rightHeights[i+1], warehouse[i]);
    }
    
    // Sort boxes
    qsort(boxes, boxesSize, sizeof(int), compare);
    
    // Use two pointers
    int left = 0;
    int right = n - 1;
    int count = 0;
    
    for (int i = 0; i < boxesSize; i++) {
        int box = boxes[i];
        // Try to place from the side with higher effective height
        if (left <= right) {
            if (leftHeights[left] >= box && (right >= n || leftHeights[left] >= rightHeights[right])) {
                left++;
                count++;
            } else if (rightHeights[right] >= box) {
                right--;
                count++;
            }
        }
    }
    
    free(leftHeights);
    free(rightHeights);
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int boxes[1000], boxesSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            boxes[boxesSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    fgets(line, sizeof(line), stdin);
    int warehouse[1000], warehouseSize = 0;
    token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            warehouse[warehouseSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(boxes, boxesSize, warehouse, warehouseSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n) to calculate effective heights + O(n log n) to sort boxes + O(n) for two pointers

⚡ Linearithmic

Space Complexity

O(n)

Arrays to store effective heights from left and right directions

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler