Maximum Height by Stacking Cuboids - Video Solutions

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.