Maximum Height by Stacking Cuboids solution and explanation
Google
9 more videos on this problem
Leetcode 1691. Maximum Height by Stacking CuboidsFraz · 12:32 · 4K views
LeetCode 1691. Maximum Height by Stacking CuboidsHappy Coding · 23:00 · 1K views
【每日一题】1691. Maximum Height by Stacking Cuboids, 12/16/2020Huifeng Guan · 49:26 · 748 views
1691. Maximum Height by Stacking Cuboids (Leetcode Hard)Programming Live with Larry · 30:25 · 518 views
LeetCode Q 1691. Maximum Height by Stacking CuboidsSweet AI · 10:31 · 237 views
Solving Box Stacking Problem with DP: LeetCode 1691 Explained!Akshay Gautam · 17:46 · 214 views
Leetcode 1691. Maximum Height by Stacking CuboidsFearless Learner · 13:33 · 135 views
LeetCode 1691: Maximum Height by Stacking CuboidsAlitaCode · 29:56 · 9 views
ข้อ 1691. Maximum Height by Stacking Cuboids | LeetCodeThakorn Jareonrat · 13:08 · 5 views
Lecture 120: Maximum Height by Stacking Cuboid || DP SeriesCodeHelp - by Babbar · 16:10 · 47K views
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.
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.
def maxHeight(cuboids):
for cuboid in cuboids:
cuboid.sort()
cuboids.sort()
n = len(cuboids)
dp = [0] * n
maxH = 0
for i in range(n):
dp[i] = cuboids[i][2]
for j in range(i):
if cuboids[j][0] <= cuboids[i][0] \
and cuboids[j][1] <= cuboids[i][1] \
and cuboids[j][2] <= cuboids[i][2]:
dp[i] = max(dp[i], dp[j] + cuboids[i][2])
maxH = max(maxH, dp[i])
return maxH
# Example usage:
cuboids = [[50, 45, 20], [95, 37, 53], [45, 23, 12]]
print(maxHeight(cuboids))import java.util.Arrays;
public class Main {
public int maxHeight(int[][] cuboids) {
for (int[] cuboid : cuboids)
Arrays.sort(cuboid);
Arrays.sort(cuboids, (a, b) -> {
if (a[0] != b[0]) return a[0] - b[0];
if (a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
});
int n = cuboids.length;
int[] dp = new int[n];
int maxH = 0;
for (int i = 0; i < n; i++) {
dp[i] = cuboids[i][2];
for (int j = 0; j < i; j++) {
if (cuboids[j][0] <= cuboids[i][0] &&
cuboids[j][1] <= cuboids[i][1] &&
cuboids[j][2] <= cuboids[i][2]) {
dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
}
}
maxH = Math.max(maxH, dp[i]);
}
return maxH;
}
public static void main(String[] args) {
Main obj = new Main();
int[][] cuboids = {{50, 45, 20}, {95, 37, 53}, {45, 23, 12}};
System.out.println(obj.maxHeight(cuboids));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxHeight(vector<vector<int>>& cuboids) {
for (auto& cuboid : cuboids)
sort(cuboid.begin(), cuboid.end());
sort(cuboids.begin(), cuboids.end());
int n = cuboids.size();
vector<int> dp(n, 0);
int maxH = 0;
for (int i = 0; i < n; i++) {
dp[i] = cuboids[i][2];
for (int j = 0; j < i; j++) {
if (cuboids[j][0] <= cuboids[i][0] &&
cuboids[j][1] <= cuboids[i][1] &&
cuboids[j][2] <= cuboids[i][2]) {
dp[i] = max(dp[i], dp[j] + cuboids[i][2]);
}
}
maxH = max(maxH, dp[i]);
}
return maxH;
}
int main() {
vector<vector<int>> cuboids = {{50, 45, 20}, {95, 37, 53}, {45, 23, 12}};
cout << maxHeight(cuboids) << endl;
return 0;
}function maxHeight(cuboids) {
cuboids.forEach(cuboid => cuboid.sort((a, b) => a - b));
cuboids.sort((a, b) => {
if (a[0] !== b[0]) return a[0] - b[0];
if (a[1] !== b[1]) return a[1] - b[1];
return a[2] - b[2];
});
const n = cuboids.length;
const dp = Array(n).fill(0);
let maxH = 0;
for (let i = 0; i < n; i++) {
dp[i] = cuboids[i][2];
for (let j = 0; j < i; j++) {
if (cuboids[j][0] <= cuboids[i][0] &&
cuboids[j][1] <= cuboids[i][1] &&
cuboids[j][2] <= cuboids[i][2]) {
dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
}
}
maxH = Math.max(maxH, dp[i]);
}
return maxH;
}
const cuboids = [[50, 45, 20], [95, 37, 53], [45, 23, 12]];
console.log(maxHeight(cuboids));#include <stdio.h>
#include <string.h>
#define MAX 100
int maxHeight(int cuboids[MAX][3], int n) {
for (int i = 0; i < n; i++) {
// Sort each cuboid's dimensions
if (cuboids[i][0] > cuboids[i][1]) { int t = cuboids[i][0]; cuboids[i][0] = cuboids[i][1]; cuboids[i][1] = t; }
if (cuboids[i][1] > cuboids[i][2]) { int t = cuboids[i][1]; cuboids[i][1] = cuboids[i][2]; cuboids[i][2] = t; }
if (cuboids[i][0] > cuboids[i][1]) { int t = cuboids[i][0]; cuboids[i][0] = cuboids[i][1]; cuboids[i][1] = t; }
}
// Sort cuboids array
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (cuboids[i][0] > cuboids[j][0] ||
(cuboids[i][0] == cuboids[j][0] && cuboids[i][1] > cuboids[j][1]) ||
(cuboids[i][0] == cuboids[j][0] && cuboids[i][1] == cuboids[j][1] && cuboids[i][2] > cuboids[j][2])) {
int temp;
for (int k = 0; k < 3; k++) {
temp = cuboids[i][k];
cuboids[i][k] = cuboids[j][k];
cuboids[j][k] = temp;
}
}
}
}
int dp[MAX], maxH = 0;
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++) {
dp[i] = cuboids[i][2];
for (int j = 0; j < i; j++) {
if (cuboids[j][0] <= cuboids[i][0] && cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
dp[i] = fmax(dp[i], dp[j] + cuboids[i][2]);
}
}
maxH = fmax(maxH, dp[i]);
}
return maxH;
}
int main() {
int cuboids[MAX][3] = {{50, 45, 20}, {95, 37, 53}, {45, 23, 12}};
int n = 3;
printf("%d\n", maxHeight(cuboids, n));
return 0;
}using System;
using System.Linq;
public class Solution {
public int MaxHeight(int[][] cuboids) {
foreach (var cuboid in cuboids)
Array.Sort(cuboid);
Array.Sort(cuboids, (a, b) => {
if (a[0] != b[0]) return a[0] - b[0];
if (a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
});
int n = cuboids.Length;
int[] dp = new int[n];
int maxH = 0;
for (int i = 0; i < n; i++) {
dp[i] = cuboids[i][2];
for (int j = 0; j < i; j++) {
if (cuboids[j][0] <= cuboids[i][0] &&
cuboids[j][1] <= cuboids[i][1] &&
cuboids[j][2] <= cuboids[i][2]) {
dp[i] = Math.Max(dp[i], dp[j] + cuboids[i][2]);
}
}
maxH = Math.Max(maxH, dp[i]);
}
return maxH;
}
public static void Main() {
var solution = new Solution();
int[][] cuboids = new int[][] {
new int[] {50, 45, 20}, new int[] {95, 37, 53}, new int[] {45, 23, 12}
};
Console.WriteLine(solution.MaxHeight(cuboids));
}
}This Python solution sorts each cuboid and the list itself, ensuring the cuboids are optimally aligned and ready for constraint checking through dynamic programming. Each step computes the maximum height achievable by adding current cuboid height to the best-found combinations in previous iterations.
Time Complexity: O(n^2), comparisons in nested loop.
Space Complexity: O(n), for 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.
def maxHeight(cuboids):
for cuboid in cuboids:
cuboid.sort()
cuboids.sort()
dp = [-1] * len(cuboids)
def height(i):
if dp[i] != -1:
return dp[i]
maxH = cuboids[i][2]
for j in range(i + 1, len(cuboids)):
if cuboids[i][0] <= cuboids[j][0] and \
cuboids[i][1] <= cuboids[j][1] and \
cuboids[i][2] <= cuboids[j][2]:
maxH = max(maxH, cuboids[i][2] + height(j))
dp[i] = maxH
return maxH
maxHeight = 0
for i in range(len(cuboids)):
maxHeight = max(maxHeight, height(i))
return maxHeight
# Example usage:
cuboids = [[50, 45, 20], [95, 37, 53], [45, 23, 12]]
print(maxHeight(cuboids))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.
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.
function maxHeight(cuboids: number[][]): number {
for (const c of cuboids) {
c.sort((a, b) => a - b);
}
cuboids.sort((a, b) => {
if (a[0] !== b[0]) {
return a[0] - b[0];
}
if (a[1] !== b[1]) {
return a[1] - b[1];
}
return a[2] - b[2];
});
const n = cuboids.length;
const f = Array(n).fill(0);
for (let i = 0; i < n; ++i) {
for (let j = 0; j < i; ++j) {
const ok = cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2];
if (ok) f[i] = Math.max(f[i], f[j]);
}
f[i] += cuboids[i][2];
}
return Math.max(...f);
}func maxHeight(cuboids [][]int) int {
for _, c := range cuboids {
sort.Ints(c)
}
sort.Slice(cuboids, func(i, j int) bool {
a, b := cuboids[i], cuboids[j]
return a[0] < b[0] || a[0] == b[0] && (a[1] < b[1] || a[1] == b[1] && a[2] < b[2])
})
n := len(cuboids)
f := make([]int, n)
for i := range f {
for j := 0; j < i; j++ {
if cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2] {
f[i] = max(f[i], f[j])
}
}
f[i] += cuboids[i][2]
}
return slices.Max(f)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Pre-sorting | Time Complexity: O(n^2), comparisons in nested loop. |
| Greedy with Recursive Backup | Time Complexity: O(n^2), determined by recursion loop combinations. |
| Sorting + Dynamic Programming | – |
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 |
Frequently asked questions
Is Maximum Height by Stacking Cuboids easy or hard?
The problem is classified as Hard because it requires recognizing that cuboid rotations can be normalized and that the stacking condition becomes a weighted LIS problem. Without that insight, brute-force exploration grows exponentially and becomes impractical.
Maximum Height by Stacking Cuboids Python/Java solution
Python and Java implementations typically follow the same steps: normalize cuboid dimensions with sorting, sort the cuboid list, and apply an O(n^2) DP similar to longest increasing subsequence. The DP stores cumulative heights and updates whenever a valid stacking condition is met.
How to solve Maximum Height by Stacking Cuboids in O(n^2)?
First sort the dimensions inside each cuboid so rotations are implicitly handled. Then sort the list of cuboids lexicographically. Use dynamic programming where dp[i] stores the maximum height with cuboid i on top. For each i, check all j < i and update dp[i] if cuboid j can support cuboid i. The final answer is the maximum value in the dp array.
Is Maximum Height by Stacking Cuboids asked at Google/Amazon/Meta?
Stacking and box-arrangement problems appear frequently in interviews at companies like Amazon, Google, and Meta because they test dynamic programming and sorting insights. Variants such as Box Stacking or LIS-based stacking problems are common interview exercises.
What is the best approach for Maximum Height by Stacking Cuboids ?
The most effective approach is dynamic programming with pre-sorting. Each cuboid’s dimensions are sorted, then all cuboids are sorted lexicographically. A DP array computes the maximum stack height where dp[i] represents the tallest stack ending with cuboid i. This reduces the problem to a weighted LIS-style comparison and runs in O(n^2) time with O(n) space.
What data structure is used in Maximum Height by Stacking Cuboids ?
The solution primarily uses arrays and a dynamic programming table. Sorting is applied to both cuboid dimensions and the overall list of cuboids. The DP array tracks the best achievable height for each cuboid when placed at the top of a stack.
What is the time complexity of Maximum Height by Stacking Cuboids ?
The optimal dynamic programming solution runs in O(n^2) time because each cuboid is compared with all previous cuboids to determine stacking compatibility. Sorting the cuboids adds O(n log n), but the DP step dominates overall complexity. Space complexity is O(n) for the DP array storing stack heights.