MediumNo. 1564LeetCode Premium
Put Boxes Into the Warehouse I — LeetCode 1564 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Sorting
- Reading time
- 3 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 labelled from 0 to n - 1 from left to right where warehouse[i] (0-indexed) is the height of the ith room.
Example
- Input
- boxes = [4,3,4,1], warehouse = [5,3,3,4,1]
- Output
- 3
- Explanation
- We can first put the box of height 1 in room 4. Then we can put the box of height 3 in either of the 3 rooms 1, 2, or 3. Lastly, we can put one box of height 4 in room 0.
Python solution
class Solution:
def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
n = len(warehouse)
left = [warehouse[0]] * n
for i in range(1, n):
left[i] = min(left[i - 1], warehouse[i])
boxes.sort()
i, j = 0, n - 1
while i < len(boxes):
while j >= 0 and left[j] < boxes[i]:
j -= 1
if j < 0:
break
i, j = i + 1, j - 1
return iComplexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1564. Put Boxes Into the Warehouse I 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 |
|---|---|---|
| 1561 | Maximum Number of Coins You Can Get | 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 1564. Put Boxes Into the Warehouse I?
LeetCode 1564. Put Boxes Into the Warehouse I is rated Medium on LeetCode.
- What topics does LeetCode 1564. Put Boxes Into the Warehouse I cover?
LeetCode 1564. Put Boxes Into the Warehouse I is tagged Greedy, Array and Sorting on LeetCode.
- Is LeetCode 1564. Put Boxes Into the Warehouse I a premium problem?
Yes. LeetCode 1564. Put Boxes Into the Warehouse I is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.