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 <= 100Problem 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.
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.
Time Complexity: O(n^2), as the cuboids are compared pairwise.
Space Complexity: O(n), used for the dp array.
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.
Python
Time Complexity: O(n^2), determined by recursion loop combinations.
Space Complexity: O(n), from recursive depth and dp uses.
| 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. |
| 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 |
Leetcode 1691. Maximum Height by Stacking Cuboids • Fraz • 4,043 views views
Watch 9 more video solutions →Practice Maximum Height by Stacking Cuboids with our built-in code editor and test cases.
Practice on FleetCode