{x}
blog image

Maximum Height by Stacking Cuboids

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.length
  • 1 <= n <= 100
  • 1 <= widthi, lengthi, heighti <= 100

Solution Explanation: Maximum Height by Stacking Cuboids

This problem asks for the maximum height achievable by stacking a subset of given cuboids, subject to constraints on their dimensions. The key insight lies in the fact that we can rotate the cuboids, and a clever sorting strategy coupled with dynamic programming can efficiently solve this.

Approach:

  1. Normalization: For each cuboid, we sort its dimensions (width, length, height) in ascending order. This ensures a consistent orientation, simplifying comparison and stacking. We now treat the smallest dimension as "length", the middle as "width", and the largest as "height".

  2. Sorting Cuboids: We sort all the cuboids based on their dimensions. This sorting order is crucial for the dynamic programming step. The preferred sorting is lexicographical, first by length, then width, then height. This ordering helps optimize the DP process because if cuboid A's dimensions are all less than or equal to cuboid B's dimensions, then A can be stacked on top of B.

  3. Dynamic Programming: We use dynamic programming to find the maximum height. We create a DP array f where f[i] stores the maximum height achievable using cuboid i as the bottommost cuboid.

    • Base Case: f[i] is initialized to the height of cuboid i.

    • State Transition: To find f[i], we iterate through cuboids with indices j less than i. If cuboid j can be stacked on top of cuboid i (meaning cuboids[j][0] <= cuboids[i][0] and cuboids[j][1] <= cuboids[i][1]), then we update f[i] using f[i] = max(f[i], f[j] + cuboids[i][2]). This means we consider stacking the maximum height achieved up to cuboid j on top of cuboid i.

  4. Result: The final answer is the maximum value in the f array, representing the maximum height achievable among all possible stackings.

Time and Space Complexity:

  • Time Complexity: O(N^2), where N is the number of cuboids. This is dominated by the nested loops in the dynamic programming step.
  • Space Complexity: O(N) to store the DP array f.

Code Examples (Python):

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        for cuboid in cuboids:
            cuboid.sort()  # Normalize each cuboid's dimensions
        cuboids.sort()  # Sort cuboids lexicographically
 
        n = len(cuboids)
        dp = [0] * n
        for i in range(n):
            dp[i] = cuboids[i][2]  # Initialize with the height of the cuboid
 
            for j in range(i):
                if cuboids[j][0] <= cuboids[i][0] and cuboids[j][1] <= cuboids[i][1]:
                    dp[i] = max(dp[i], dp[j] + cuboids[i][2])
 
        return max(dp)

The code in other languages (Java, C++, Go, TypeScript, Javascript) follows the same algorithm, differing only in syntax and specific library functions used for sorting and finding the maximum value. The core logic remains identical.