Maximum Height By Stacking Cuboids - Leetcode Solution

The Maximum Height By Stacking Cuboids problem on LeetCode asks us to find the maximum possible height of a stack of cuboids, given a set of cuboids with their dimensions. The stack must follow certain rules, including that each cuboid in the stack must have a strictly smaller width, height, and depth than the cuboid below it. We can use dynamic programming to solve this problem efficiently.

Approach:

1. Sort the cuboids in decreasing order of their dimensions (width, height, depth).
2. Create an array dp of length n, where n is the number of cuboids provided. Initialize each value of dp to be the height of the corresponding cuboid, as any cuboid can form a stack of height equal to its own height.
3. For each pair of cuboids (i, j) where i < j, check if cuboid i can be placed on top of cuboid j. If the dimensions of cuboid i are strictly smaller than cuboid j in all three dimensions, then it is possible to place cuboid i on top of cuboid j. In this case, the height of the stack consisting of cuboid j at the bottom and cuboid i on top would be dp[i] + height[j].
4. After checking all pairs of cuboids, find the maximum value in the dp array. This is the maximum height of the stack of cuboids.

Let's look at the implementation of the above approach:

def maxHeight(cuboids):
    # sort the cuboids in decreasing order of their dimensions
    cuboids.sort(reverse=True)
    n = len(cuboids)
    dp = [cuboid[2] for cuboid in cuboids] # initialize dp with each cuboid's height
    
    for i in range(n):
        for j in range(i+1, n):
            if cuboids[i][0] <= cuboids[j][0] and cuboids[i][1] <= cuboids[j][1] and cuboids[i][2] <= cuboids[j][2]:
                dp[i] = max(dp[i], dp[j] + cuboids[i][2])
    
    return max(dp) # return the maximum height of the stack
    
    
# test the function with an example
cuboids = [[50, 45, 20], [95, 37, 53], [45, 23, 12]]
print(maxHeight(cuboids)) # output: 190

In the above implementation, we first sort the cuboids in decreasing order of their dimensions. We then create an array dp of length n, where n is the number of cuboids provided, and initialize each value of dp to be the height of the corresponding cuboid.

We then iterate over all possible pairs of cuboids (i, j) where i < j and check if cuboid i can be placed on top of cuboid j, based on the rules mentioned in the problem statement. If it is possible to place cuboid i on top of cuboid j, then the height of the stack consisting of cuboid j at the bottom and cuboid i on top would be dp[i] + height[j]. We update dp[i] if this height is greater than the current value of dp[i].

After checking all pairs of cuboids, we find the maximum value in the dp array, which is the maximum height of the stack of cuboids, and return it.

In the above example, the maximum height of the stack is 190, which can be achieved by arranging the cuboids in the following order (from bottom to top): [95, 37, 53], [50, 45, 20], [45, 23, 12]. Note that there could be multiple valid arrangements of the cuboids to maximize the height, but the above implementation guarantees to find the maximum possible height.

1