MediumNo. 1580LeetCode Premium
Put Boxes Into the Warehouse II — LeetCode 1580 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Sorting
- Reading time
- 4 min
- Source
- leetcode.com
The 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.
Example
- Input
- boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
- Output
- 4
- Explanation
- We can store the boxes in the following order:
Python solution
class Solution:
def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
n = len(warehouse)
left = [0] * n
right = [0] * n
left[0] = right[-1] = inf
for i in range(1, n):
left[i] = min(left[i - 1], warehouse[i - 1])
for i in range(n - 2, -1, -1):
right[i] = min(right[i + 1], warehouse[i + 1])
for i in range(n):
warehouse[i] = min(warehouse[i], max(left[i], right[i]))
boxes.sort()
warehouse.sort()
ans = i = 0
for x in boxes:
while i < n and warehouse[i] < x:
i += 1
if i == n:
break
ans, i = ans + 1, i + 1
return ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1580. Put Boxes Into the Warehouse II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1589 | Maximum Sum Obtained of Any Permutation | Medium |
| 0179 | Largest Number | Medium |
| 0324 | Wiggle Sort II | Medium |
| 0452 | Minimum Number of Arrows to Burst Balloons | Medium |
| 0455 | Assign Cookies | Easy |
| 0502 | IPO | Hard |
Frequently asked questions
- How hard is LeetCode 1580. Put Boxes Into the Warehouse II?
LeetCode 1580. Put Boxes Into the Warehouse II is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1580. Put Boxes Into the Warehouse II?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 1580. Put Boxes Into the Warehouse II?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1580. Put Boxes Into the Warehouse II cover?
LeetCode 1580. Put Boxes Into the Warehouse II is tagged Greedy, Array and Sorting on LeetCode.
- Is LeetCode 1580. Put Boxes Into the Warehouse II a premium problem?
Yes. LeetCode 1580. Put Boxes Into the Warehouse II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.