Problem Description

You are given a list of cuboids, where each cuboid is represented by a list of three integers: [width, length, height]. You can stack cuboids on top of each other to form a tower, but you must follow these rules:

• You can rotate any cuboid so that its dimensions are in any order, but after rotation, the width, length, and height must be assigned to some sides.
• You can stack cuboid A on top of cuboid B only if the width, length, and height of A are each less than or equal to those of B (i.e., A fits on B).
• You cannot reuse the same cuboid in multiple places in the stack.

Your task is to return the maximum possible height of a stack that can be formed by stacking some or all of the cuboids.

Key constraints: Each cuboid can be rotated, but can be used only once. You must determine the optimal order (and orientation) to maximize the total height.

Thought Process

At first glance, it seems like a brute-force approach would be to try all possible combinations and rotations of cuboids, checking which ones can be stacked and keeping track of the tallest possible tower. But with up to 100 cuboids and 6 possible rotations for each, this quickly becomes infeasible.

To optimize, we need to:

• Realize that the order of stacking matters, and that after rotation, each cuboid can be represented in a "canonical" orientation (e.g., sorted dimensions).
• Notice that the problem is similar to the "Longest Increasing Subsequence" (LIS), but in three dimensions (width, length, height) and the "increase" is actually "non-increasing" because the top cuboid must be smaller or equal in all dimensions.
• Think of dynamic programming: for each cuboid, keep track of the tallest stack ending with that cuboid, and update the answer as we consider each possible base cuboid.

This shift from brute-force to dynamic programming is the key insight for an efficient solution.

Solution Approach

Here’s a step-by-step breakdown of the optimal approach:

1. Normalize Cuboid Orientations:
   • For each cuboid, sort its dimensions so that width ≤ length ≤ height. This way, rotation is handled, and we only need to consider one orientation per cuboid.
2. Sort Cuboids:
   • Sort all cuboids in non-decreasing order by their dimensions (first by width, then length, then height). This helps us to always try stacking smaller cuboids on larger ones.
3. Dynamic Programming:
   • Let dp[i] represent the maximum height of a stack ending with cuboid i at the top.
   • Initialize each dp[i] as the height of cuboid i itself.
   • For each cuboid i, look at all cuboids j before it (i.e., j < i), and if cuboid i can be placed on j (all dimensions of i ≤ j), update dp[i] as max(dp[i], dp[j] + height of i).
4. Result:
   • The answer is the maximum value in the dp array.

This approach ensures we efficiently consider all valid stacking orders and orientations.

Example Walkthrough

Sample Input:
cuboids = [[50,45,20], [95,37,53], [45,23,12]]

1. Sort each cuboid:
   • [20, 45, 50]
   • [37, 53, 95]
   • [12, 23, 45]
2. Sort all cuboids:
   • [12, 23, 45]
   • [20, 45, 50]
   • [37, 53, 95]
3. Initialize DP:
   • dp = [45, 50, 95]
4. Stacking:
   • Can [20,45,50] go on [12,23,45]? No (20>12, 45>23, 50>45), so skip.
   • Can [37,53,95] go on [12,23,45]? No.
   • Can [37,53,95] go on [20,45,50]? No.
   • But [12,23,45] can be base, then [20,45,50], then [37,53,95].
   • So, try stacking in reverse: [37,53,95] as base, [20,45,50] on top, [12,23,45] on top of that.
   • Each time, check if the upper cuboid fits (all dimensions ≤ to those below).
5. Update DP:
   • dp[1] = max(50, 45+50) = 95 (if [20,45,50] can go on [12,23,45])
   • dp[2] = max(95, 95+45 or 95+50 if stacking is possible)
6. Result:
   • The maximum height is 190.

This example shows how the DP array is built up and how the tallest stack is found.

Time and Space Complexity

• Brute-force approach:
  • Try all permutations and rotations: O((n!) * 6^n), which is infeasible for n up to 100.
• Optimized DP approach:
  • Sorting cuboids: O(n log n)
  • DP: For each cuboid, check all previous ones: O(n^2)
  • Total: O(n^2) time and O(n) space for the DP array.

The optimized approach is efficient and feasible for the input constraints.

Summary

To solve the "Maximum Height by Stacking Cuboids" problem, we:

• Normalize cuboid orientations by sorting dimensions
• Sort cuboids to allow efficient stacking checks
• Use dynamic programming to build up the tallest possible stack ending at each cuboid
• Return the maximum stack height found

The elegance of this solution lies in reducing a seemingly complex 3D stacking problem to a variant of the Longest Increasing Subsequence, making it both efficient and easy to implement.

Code Implementation

class Solution:
    def maxHeight(self, cuboids):
        # Step 1: Normalize all cuboids by sorting their dimensions
        for cuboid in cuboids:
            cuboid.sort()
        # Step 2: Sort cuboids in non-decreasing order
        cuboids.sort()
        n = len(cuboids)
        dp = [0] * n
        for i in range(n):
            dp[i] = cuboids[i][2]  # height after sorting
            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)
      

class Solution {
public:
    int maxHeight(vector<vector<int>>& cuboids) {
        for (auto& c : cuboids) sort(c.begin(), c.end());
        sort(cuboids.begin(), cuboids.end());
        int n = cuboids.size();
        vector<int> dp(n, 0);
        int res = 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]);
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};
      

class Solution {
    public int maxHeight(int[][] cuboids) {
        for (int[] c : cuboids) Arrays.sort(c);
        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 res = 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]);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
      

var maxHeight = function(cuboids) {
    cuboids.forEach(c => 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];
    });
    let n = cuboids.length;
    let dp = new Array(n).fill(0);
    let res = 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]);
            }
        }
        res = Math.max(res, dp[i]);
    }
    return res;
};