Put Boxes Into the Warehouse I - Practice Coding Problems

Put Boxes Into the Warehouse I - 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 labelled 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.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Effective heights are [5,3,3,3,3]. Sort boxes to [1,3,4,4]. Place box 1 at position 0, box 3 at position 1, box 4 cannot fit anywhere else. Total: 3 boxes.

Example 2 — Height Constraint

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

› Output: 3

💡 Note: Effective heights are [3,3,1,1]. Sorted boxes [1,2,2,3,4]. Place box 1 at pos 0, box 2 at pos 1, then remaining boxes too tall for remaining positions.

Example 3 — All Boxes Fit

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

› Output: 3

💡 Note: All warehouse positions have height 4, so all boxes [1,2,3] can be placed. Effective heights are [4,4,4].

Constraints

n == boxes.length
m == warehouse.length
1 ≤ n, m ≤ 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,4]

Process

Compute effective heights and sort boxes for optimal placement

Output

Maximum 3 boxes can be placed

Key Takeaway

🎯 Key Insight: The effective height at each position is the minimum height encountered from the left, creating a bottleneck effect

Asked in

a Amazon 35 G Google 28

The key insight is that the effective height at each warehouse position is constrained by the minimum height encountered from the left. The optimal approach computes these effective heights in O(m) time, sorts the boxes in O(n log n), then greedily places the smallest boxes first. Time: O(n log n + m), Space: O(m)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Effective Heights	O(n log n + m)	O(m)	Precompute effective ceiling heights, then greedily match smallest suitable boxes
Try All Permutations	O(n! × n × m)	O(n)	Generate all possible orderings of boxes and test each one

Greedy with Effective Heights — Algorithm Steps

Compute effective heights by taking running minimum from left
Sort boxes in ascending order
Greedily place each box at the leftmost valid position

Visualization

Tap to expand

Step-by-Step Walkthrough

Compute Effective Heights

Find the running minimum heights from left

Sort Boxes

Sort boxes in ascending order

Greedy Placement

Place smallest boxes first at leftmost positions

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 boxCount, int* warehouse, int warehouseCount) {
    // Compute effective heights - each position limited by min height from left
    int* effectiveHeights = (int*)malloc(warehouseCount * sizeof(int));
    effectiveHeights[0] = warehouse[0];
    
    for (int i = 1; i < warehouseCount; i++) {
        effectiveHeights[i] = min(effectiveHeights[i-1], warehouse[i]);
    }
    
    // Sort boxes in ascending order for greedy placement
    qsort(boxes, boxCount, sizeof(int), compare);
    
    int count = 0;
    int pos = 0;
    
    // Greedily place each box at leftmost valid position
    for (int i = 0; i < boxCount; i++) {
        int boxHeight = boxes[i];
        // Find next position where box fits
        while (pos < warehouseCount && effectiveHeights[pos] < boxHeight) {
            pos++;
        }
        
        if (pos < warehouseCount) {
            count++;
            pos++;
        } else {
            break;
        }
    }
    
    free(effectiveHeights);
    return count;
}

int main() {
    // Simple parsing - assumes format [1,2,3]
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int boxes[100], warehouse[100];
    int boxCount = 0, warehouseCount = 0;
    
    // Parse boxes array
    char* ptr = strtok(line1, "[,]");
    while (ptr != NULL) {
        boxes[boxCount++] = atoi(ptr);
        ptr = strtok(NULL, "[,]");
    }
    
    // Parse warehouse array
    ptr = strtok(line2, "[,]");
    while (ptr != NULL) {
        warehouse[warehouseCount++] = atoi(ptr);
        ptr = strtok(NULL, "[,]");
    }
    
    int result = solution(boxes, warehouse, warehouseCount);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m)

O(n log n) to sort boxes, O(m) to precompute effective heights, O(n×m) worst case for placement

⚡ Linearithmic

Space Complexity

O(m)

Array to store effective heights for each warehouse position

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

824 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 with Effective Heights — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler