Maximum Height by Stacking Cuboids - Solution & Explanation
Problem Statement
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.
You can place cuboid i on cuboid j if widthi <= widthj and lengthi <= lengthj and heighti <= heightj. You can rearrange any cuboid's dimensions by rotating it to put it on another cuboid.
Return the maximum height of the stacked cuboids.
Example 1:
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. Cuboid 0 is placed next with the 45x20 side facing down with height 50. Cuboid 2 is placed next with the 23x12 side facing down with height 45. The total height is 95 + 50 + 45 = 190.
Example 2:
Input: cuboids = [[38,25,45],[76,35,3]] Output: 76 Explanation: You can't place any of the cuboids on the other. We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.
Example 3:
Input: cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]] Output: 102 Explanation: After rearranging the cuboids, you can see that all cuboids have the same dimension. You can place the 11x7 side down on all cuboids so their heights are 17. The maximum height of stacked cuboids is 6 * 17 = 102.
Constraints:
n == cuboids.length1 <= n <= 1001 <= widthi, lengthi, heighti <= 100
Approach Overview
Problem Overview: You are given multiple cuboids where each has three dimensions. You can rotate a cuboid so any side acts as height, and you may stack cuboids if every dimension of the upper cuboid is less than or equal to the one below it. The goal is to compute the maximum possible stack height.
Approach 1: Greedy with Recursive Backup (Exponential Time)
This approach tries to build stacks greedily and falls back to recursion when multiple stacking choices exist. For each cuboid, rotate and attempt to place it on previously chosen cuboids if all dimensions fit. If several placements are possible, recursively explore each path and keep the best height. The method relies on checking dimension compatibility and exploring combinations similar to subset/backtracking problems. Time complexity is O(2^n) in the worst case because many stacking permutations may be explored, with O(n) recursion depth for space.
Approach 2: Dynamic Programming with Pre-sorting (O(n^2))
The key insight is that cuboids can be normalized and ordered so the stacking condition becomes similar to the Longest Increasing Subsequence problem. First, sort the three dimensions of each cuboid individually so that w ≤ l ≤ h. This removes the need to explicitly consider all rotations. Next, sort all cuboids lexicographically by their dimensions. Once sorted, any valid stack must appear in this order.
Create a DP array where dp[i] represents the maximum stack height with cuboid i at the top. Iterate through cuboids, and for each cuboid i, check all previous cuboids j. If cuboid[j] can support cuboid[i] (all dimensions ≤), update dp[i] = max(dp[i], dp[j] + height[i]). This is essentially a weighted LIS where the "weight" is the cuboid height.
Sorting ensures valid stacking order and eliminates rotation complexity. The DP transition checks compatibility using simple dimension comparisons. This solution runs in O(n^2) time due to the nested iteration and uses O(n) extra space for the DP array.
Recommended for interviews: The dynamic programming approach with pre-sorting is the expected solution. It shows you recognize the transformation into an LIS-style DP after normalizing rotations. Interviewers usually expect candidates to combine ideas from sorting, array manipulation, and dynamic programming. Mentioning the brute-force recursive search demonstrates understanding of the problem space, but implementing the O(n^2) DP solution demonstrates algorithmic maturity.
Approach 1: Dynamic Programming with Pre-sorting
Sort each cuboid internally and sort the list of cuboids based on dimensions. Use a dynamic programming approach where dp[i] represents the maximum height achievable using the cuboid set starting from the ith cuboid. Iterate through each cuboid and for every pair of cuboids, check if one can be placed on the other. Update the dp array accordingly and find the maximum value in the dp array for the solution.
This C solution first sorts each cuboid's dimensions to allow any of them to be used as height, width, or length. It then sorts all the cuboids by their dimensions to ease the stacking process. A dynamic programming array dp is used where dp[i] is the maximum height achieved by stacking up to the ith cuboid. By checking all pairs (i, j) and updating dp[i] appropriately, it derives the maximum stacked height.
Complexity
Time Complexity: O(n^2), as the cuboids are compared pairwise.
Space Complexity: O(n), used for the dp array.
Approach 2: Greedy with Recursive Backup
This approach involves choosing larges cuboids possible at the base and using recursion to user smaller ones above it. If bottleneck is reached, backtrack to different stacking configurations.
This Python function uses both sorting and recursive memoization. It computes possible heights recursively and stores it in the dp array to prevent recomputation and ensure maximum stacking height determination efficiently.
Code
Python
Complexity
Time Complexity: O(n^2), determined by recursion loop combinations.
Space Complexity: O(n), from recursive depth and dp uses.
Approach 3: Sorting + Dynamic Programming
According to the problem description, box j can be placed on box i if and only if the "length, width, and height" of box j are less than or equal to the "length, width, and height" of box i.
This problem allows us to rotate the boxes, which means we can choose any side of the box as the "height". For any legal stacking, if we rotate each box in it to "length <= width <= height", the stacking is still legal and can ensure the maximum height of the stacking.
Therefore, we can sort all the sides of the boxes so that each box satisfies "length <= width <= height". Then we sort each box in ascending order.
Next, we can use dynamic programming to solve this problem.
We define f[i] as the maximum height when box i is at the bottom. We can enumerate each box j above box i, where 0 leq j < i. If j can be placed on top of i, then we can get the state transition equation:
$
f[i] = max_{0 leq j < i} {f[j] + h[i]}
where h[i] represents the height of box i.
The final answer is the maximum value of f[i].
The time complexity is O(n^2), and the space complexity is O(n). Here, n$ is the number of boxes.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Pre-sorting | Time Complexity: O(n^2), as the cuboids are compared pairwise. |
| Greedy with Recursive Backup | Time Complexity: O(n^2), determined by recursion loop combinations. |
| Sorting + Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Recursive Backup | O(2^n) | O(n) | Conceptual exploration or very small input sizes where brute-force stacking combinations are manageable |
| Dynamic Programming with Pre-sorting | O(n^2) | O(n) | General case and interview settings; optimal balance between simplicity and performance |
Video Solution
Lecture 120: Maximum Height by Stacking Cuboid || DP Series • CodeHelp - by Babbar • 47,862 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Height by Stacking Cuboids easy or hard?
Maximum Height by Stacking Cuboids Python/Java solution
How to solve Maximum Height by Stacking Cuboids in O(n^2)?
Is Maximum Height by Stacking Cuboids asked at Google/Amazon/Meta?
What is the best approach for Maximum Height by Stacking Cuboids ?
What data structure is used in Maximum Height by Stacking Cuboids ?
What is the time complexity of Maximum Height by Stacking Cuboids ?
Ready to solve this problem?
Practice Maximum Height by Stacking Cuboids with our built-in code editor and test cases.
Practice on FleetCode