Maximum Height by Stacking Cuboids

Maximum Height by Stacking Cuboids

What is this problem about?

The Maximum Height by Stacking Cuboids coding problem gives you a list of cuboids with dimensions [width, length, height]. You can rotate each cuboid in any orientation. You can stack a cuboid on top of another if all three dimensions of the top cuboid are less than or equal to the corresponding dimensions of the bottom cuboid (after choosing orientations optimally). Find the maximum achievable total height.

Why is this asked in interviews?

Samsung, Meta, Amazon, and Google use this problem to test insight-driven dynamic programming. The key insight — that you should always orient each cuboid so its smallest dimension is the height — reduces the problem to a 3D variant of the Longest Increasing Subsequence (LIS). Candidates who immediately recognize this transformation demonstrate the ability to reduce problems to known patterns, a critical interview skill.

Algorithmic pattern used

The solution uses sorting + Dynamic Programming (similar to LIS). First, for each cuboid, sort its three dimensions so the largest is the height (since maximizing height is the goal and a cuboid can only go under one with all three dimensions ≥ its own). Then sort all cuboids. Define dp[i] = maximum height achievable with cuboid i on top. For each i, check all j < i where cuboid j can be placed under cuboid i, and update: dp[i] = max(dp[i], dp[j] + height[i]). The answer is max of all dp[i].

Example explanation

Cuboids: [[2,3,4], [1,2,3]]

• After sorting dimensions: [[2,3,4], [1,2,3]]
• Sort cuboids: [[1,2,3], [2,3,4]]
• dp[0] = 3 (height of cuboid 0 alone)
• dp[1]: can [1,2,3] go under [2,3,4]? 1≤2, 2≤3, 3≤4 ✓. dp[1] = dp[0] + 4 = 7.
• Answer = 7.

Common mistakes candidates make

• Not sorting dimensions within each cuboid: Forgetting this step leads to incorrect stacking checks.
• Checking only one or two dimensions: The stacking condition requires all three dimensions to be ≤, not just height.
• Sorting cuboids incorrectly: Must sort by all three dimensions to ensure the DP ordering is valid.

Interview preparation tip

For the Array Sorting Dynamic Programming interview pattern, recognize that "can A go under B" defines a partial order, and maximizing height over a chain in this order is exactly the weighted LIS problem. Whenever you see "stack items with dimension constraints," immediately think LIS-style DP.