We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Height by Stacking Cuboids

Difficulty: Hard

Problem Description

Given n cuboids where the dimensions of the i-th cuboid is cuboids[i] = [width_i, length_i, height_i] (0-indexed). Choose a subset of cuboids and place them on each other. You can place cuboid i on cuboid j if width_i <= width_j and length_i <= length_j and height_i <= height_j. You can rearrange any cuboid's dimensions by rotating it to put it on another cuboid. Return the maximum height of the stacked cuboids.

Key Insights

  • Each cuboid can be rotated, allowing for three possible orientations.
  • A cuboid can only be placed on another cuboid if its dimensions are less than or equal to the dimensions of the cuboid below.
  • The problem can be approached using dynamic programming by sorting the cuboids and then calculating the maximum height that can be achieved by stacking them.

Space and Time Complexity

Time Complexity: O(n^2), where n is the number of cuboids, due to the nested iteration to calculate the maximum height. Space Complexity: O(n), for storing the maximum heights of stacked cuboids.

Solution

The solution involves the following steps:

  1. Normalize the dimensions of each cuboid by sorting the width, length, and height.
  2. Sort the list of cuboids based on width and then length (and height if necessary).
  3. Use dynamic programming to find the maximum height achievable by stacking cuboids. For each cuboid, check all previous cuboids to see if it can be placed on top of them and update the maximum height accordingly.

Code Solutions

def maxHeight(cuboids):
    # Normalize the dimensions of each cuboid
    for i in range(len(cuboids)):
        cuboids[i].sort()
    
    # Sort cuboids by width, then by length, then by height
    cuboids.sort()
    
    n = len(cuboids)
    dp = [0] * n
    
    # Calculate maximum height for each cuboid
    for i in range(n):
        dp[i] = cuboids[i][2]  # height of the current cuboid
        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)
← Back to All Questions