Maximum Height by Stacking Cuboids: DP with Sorting

You are given n cuboids, each defined by three dimensions: width, length, and height. You can place cuboid i on top of cuboid j if width[i] <= width[j], length[i] <= length[j], and height[i] <= height[j]. You can rearrange any cuboid's dimensions by rotating it. Find the maximum total height of a stack of cuboids.

This is LeetCode 1691: Maximum Height by Stacking Cuboids, a hard problem that combines sorting with a longest increasing subsequence (LIS) style DP. Once you see the connection to LIS, the problem becomes much more approachable.

Why this problem matters

Stacking problems show up in many forms across DP interviews. You might see them as Russian Doll Envelopes, box stacking, or cuboid stacking. They all share the same core: sort first, then run an LIS-style DP to find the longest (or tallest) valid chain. If you understand this pattern for cuboids, you can adapt it to any dimensionality.

This problem also tests whether you can identify when rearranging inputs (here, rotating cuboids) simplifies the constraint checking. That insight, sort the dimensions within each cuboid, is the key that unlocks the clean DP.

The key insight

The problem says you can rotate cuboids freely. That means for a cuboid with dimensions [a, b, c], you can orient it in any way. The optimal strategy is to always make the largest dimension the height, since you want to maximize total height.

Here is the full insight in three parts:

1. Sort dimensions within each cuboid. After sorting, the third value is always the largest, so it becomes the height. This standardizes the orientation.
2. Sort all cuboids lexicographically. This ensures that if cuboid j can serve as a base for cuboid i, then j appears before i in the sorted order.
3. Run LIS-style DP. For each cuboid i, check every previous cuboid j. If all three sorted dimensions of j are <= the corresponding dimensions of i, then i can sit on top of j.

The sorting step is critical. Without it, you would need to check every pair in both directions, and the "can stack" relationship would have no structure to exploit.

The solution

def max_height(cuboids):
    for c in cuboids:
        c.sort()
    cuboids.sort()

    n = len(cuboids)
    dp = [c[2] for c in cuboids]

    for i in range(1, n):
        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])

    return max(dp)

The first loop sorts each cuboid's dimensions in place. The second cuboids.sort() sorts all cuboids lexicographically by their three sorted dimensions. Then the nested loop is the standard LIS DP: for each cuboid i, look at every earlier cuboid j and check if j can go underneath i. If so, update dp[i] to be the maximum of its current value and dp[j] + height[i].

Visual walkthrough

The walkthrough uses cuboids [[50,45,20], [95,37,53], [45,23,12]]. After sorting dimensions within each cuboid and then sorting all cuboids, we get [[12,23,45], [20,45,50], [37,53,95]]. The DP builds up from each cuboid's own height and checks whether earlier cuboids can stack underneath. The final answer is max(dp) = 190.

Complexity analysis

Time: O(n log n + n^2). Sorting takes O(n log n). The nested DP loop takes O(n^2). The n^2 term dominates.

Space: O(n). The dp array stores one value per cuboid. Sorting is in-place.

With n up to 100 per the LeetCode constraints, O(n^2) is more than fast enough.

The building blocks

1. Sort each cuboid's dimensions

for c in cuboids:
    c.sort()

This normalizes the orientation. After sorting, c[0] <= c[1] <= c[2], and c[2] is always the height you want to maximize. Without this step, you would need to consider all 6 rotations of each cuboid separately.

2. Sort all cuboids lexicographically

cuboids.sort()

Lexicographic sorting by three keys means that if cuboid j could potentially be a base for cuboid i, j will appear at an earlier index. This is the same trick used in LIS: sort first so you only need to look backward. It also works in Russian Doll Envelopes, where you sort by width and then do LIS on heights.

3. LIS-style DP on three dimensions

for i in range(1, n):
    for j in range(i):
        if all(cuboids[j][k] <= cuboids[i][k] for k in range(3)):
            dp[i] = max(dp[i], dp[j] + cuboids[i][2])

For each cuboid i, check every previous cuboid j. The stacking condition requires all three sorted dimensions of j to be <= the corresponding dimensions of i. If the condition holds, the best stack ending at i might include j underneath. This is the same recurrence as Longest Increasing Subsequence, but generalized to three dimensions and tracking height sums instead of sequence length.

Edge cases

• Single cuboid: return its largest dimension. dp has one entry, and that is the answer.
• All identical cuboids: every cuboid can stack on every other (since all dimensions are equal). The answer is n * max_dimension.
• No cuboid can stack on another: the answer is the single tallest cuboid's height. The DP never updates past initialization.
• Cuboid with a zero dimension: [0, x, y] can go on top of anything where the other cuboid has 0 <= first_dim. The logic handles this naturally.
• Two dimensions equal, one different: for example, [1,1,5] and [1,1,3]. The condition 1 <= 1, 1 <= 1, 3 <= 5 holds, so stacking is valid.

From understanding to recall

You now know the three-step pattern: sort within, sort all, then LIS-style DP. But reading through this walkthrough is different from writing the solution cold in an interview. The tricky part is remembering why sorting within each cuboid is safe (it always maximizes the height contribution) and why the global sort makes the backward-only DP correct.

The cuboid stacking problem belongs to a family of "multi-dimensional LIS" problems. The core building block, sort-then-DP, appears across many variations. Drilling it individually with spaced repetition means you will not freeze when you see a stacking problem with different constraints or dimensions.

Related posts

• Longest Increasing Subsequence - The foundation pattern. Cuboid stacking is LIS generalized to three dimensions.
• Coin Change - Another core DP problem where you iterate over choices at each step and take the best option.
• Edit Distance - A different DP structure (2D table), but the same principle of building optimal solutions from subproblems.

If you want to internalize the sort-then-DP pattern so you can write it from memory, spaced repetition is the fastest way to get there. Practice the stacking recurrence until it is automatic, and you will recognize the same structure in dozens of interview problems.