HardNo. 1691
Maximum Height by Stacking Cuboids — LeetCode 1691 Python Solution
- Pattern
- Sorting
- Topics
- Array, Dynamic Programming, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Given n cuboids where the dimensions of the ith cuboid is cuboids[i] = [widthi, lengthi, heighti] (0-indexed). Choose a subset of cuboids and place them on each other.
Example
- Input
- cuboids = [[50,45,20],[95,37,53],[45,23,12]]
- Output
- 190
- Explanation
- Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.
Python solution
class Solution:
def maxHeight(self, cuboids: List[List[int]]) -> int:
for c in cuboids:
c.sort()
cuboids.sort()
n = len(cuboids)
f = [0] * n
for i in range(n):
for j in range(i):
if cuboids[j][1] <= cuboids[i][1] and cuboids[j][2] <= cuboids[i][2]:
f[i] = max(f[i], f[j])
f[i] += cuboids[i][2]
return max(f)Complexity
- Time
- O(n2)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1691. Maximum Height by Stacking Cuboids is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0368 | Largest Divisible Subset | Medium |
| 0435 | Non-overlapping Intervals | Medium |
| 0472 | Concatenated Words | Hard |
| 0646 | Maximum Length of Pair Chain | Medium |
| 0975 | Odd Even Jump | Hard |
| 1262 | Greatest Sum Divisible by Three | Medium |
Frequently asked questions
- How hard is LeetCode 1691. Maximum Height by Stacking Cuboids?
LeetCode 1691. Maximum Height by Stacking Cuboids is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1691. Maximum Height by Stacking Cuboids?
The Python solution on this page runs in O(n2).
- What is the space complexity of LeetCode 1691. Maximum Height by Stacking Cuboids?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1691. Maximum Height by Stacking Cuboids cover?
LeetCode 1691. Maximum Height by Stacking Cuboids is tagged Array, Dynamic Programming and Sorting on LeetCode.