#1691

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Height by Stacking Cuboids

Maximize the height of stacked cuboids by strategically rotating and stacking them using dynamic programming.

Problem Statement

Given a set of cuboids, where each cuboid is represented by three dimensions, your task is to stack a subset of these cuboids to achieve the maximum possible height. Cuboids can be rotated to change their orientation, meaning their dimensions can be rearranged. A cuboid can only be placed on top of another if its width, length, and height are all less than or equal to the cuboid below it.

Your goal is to determine the maximum height achievable by stacking cuboids. This involves sorting the cuboids in a way that allows efficient use of dynamic programming to compute the height of each potential stack configuration.

Examples

Example 1

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

Output: 190

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

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

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 Approach

State Transition Dynamic Programming

To solve this problem, use dynamic programming after sorting the cuboids. First, consider each cuboid's possible rotations and treat them as distinct items with sorted dimensions. Then, for each cuboid, check all previously processed cuboids to see if it can be placed on top of them, updating the maximum stack height accordingly.

Sorting the Cuboids

Sort the cuboids by their width, length, and height in descending order, ensuring that we process larger cuboids first. This sorting step helps in simplifying the placement conditions, as each cuboid can only be placed on another with smaller dimensions.

Maximizing Height with Dynamic Programming

After sorting the cuboids, iterate through them to calculate the maximum possible stack height for each cuboid, using previously computed values to transition and update the maximum height. The result will be the highest value found at the end of the dynamic programming process.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on both the sorting step and the dynamic programming transitions. Sorting the cuboids takes O(n log n), and for each cuboid, you may need to check all previous cuboids, making the dynamic programming step O(n^2). Thus, the total time complexity is O(n^2), where n is the number of cuboids.

What Interviewers Usually Probe

Candidate demonstrates understanding of dynamic programming with state transitions.
The candidate effectively applies sorting as a preprocessing step to optimize the solution.
The candidate chooses dynamic programming over brute force and handles cuboid rotations well.

Common Pitfalls or Variants

Common pitfalls

Forgetting to consider all rotations of the cuboids before attempting to stack them.
Not sorting the cuboids in the correct order, leading to inefficient solutions.
Attempting a brute force solution without recognizing the need for dynamic programming and state transitions.

Follow-up variants

Allow only certain rotations of cuboids.
Add constraints where the number of cuboids is much larger.
Explore optimizing space complexity in dynamic programming solutions.

FAQ

What is the main dynamic programming approach used in the Maximum Height by Stacking Cuboids problem?

The problem relies on state transition dynamic programming, where cuboids are sorted, and the maximum stack height is computed by considering previous cuboids that can be stacked on top of each other.

How can cuboids be rotated in the Maximum Height by Stacking Cuboids problem?

Each cuboid can be rotated to change its orientation, allowing for the width, length, and height to be rearranged. This gives multiple possible orientations to consider for stacking.

Why is sorting important in solving the Maximum Height by Stacking Cuboids?

Sorting the cuboids ensures that we process them in a way that allows us to efficiently calculate the maximum stack height, as cuboids with larger dimensions need to be placed first to optimize the solution.

Can I solve the Maximum Height by Stacking Cuboids problem without dynamic programming?

It is possible to solve the problem using brute force methods, but this will be much slower and inefficient compared to using dynamic programming, which optimizes the process by storing intermediate results.

What are the key challenges in the Maximum Height by Stacking Cuboids problem?

The main challenges include handling rotations efficiently, sorting the cuboids correctly, and applying dynamic programming to track the maximum achievable height.

terminal

Solution

Solution 1: Sorting + Dynamic Programming

According to the problem description, box $j$ can be placed on box $i$ if and only if the "length, width, and height" of box $j$ are less than or equal to the "length, width, and height" of box $i$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        for c in cuboids:
            c.sort()
        cuboids.sort()
        n = len(cuboids)
        f = [0] * n
        for i in range(n):
            for j in range(i):
                if cuboids[j][1] <= cuboids[i][1] and cuboids[j][2] <= cuboids[i][2]:
                    f[i] = max(f[i], f[j])
            f[i] += cuboids[i][2]
        return max(f)

Continue Practicing

#1751 maximum number of events that can be attended ii #1755 closest subsequence sum #1626 best team with no conflicts