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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Height by Stacking Cuboids

Number: 1367

Difficulty: Hard

Paid? No

Companies: Samsung

Problem Description

Given n cuboids where the i-th cuboid has dimensions cuboids[i] = [width, length, height], you can reorder the dimensions of each cuboid. Choose a subset of cuboids and stack them one on top of another such that for any cuboid placed on top of another, its dimensions are less than or equal to the ones below it. Return the maximum possible total height of the stacked cuboids.

Key Insights

  • Each cuboid’s dimensions can be rearranged. Sort the dimensions of each cuboid so that comparisons become straightforward.
  • Sort the list of cuboids (after internal sorting) by their dimensions to enforce an order that makes stacking validation efficient.
  • Use dynamic programming (DP) to build up the answer by checking, for every cuboid, which previous cuboids can support it.
  • The stacking condition is checked coordinate-wise since after sorting dimensions, the smallest two act as base dimensions and the largest as height.
  • The problem resembles the Longest Increasing Subsequence (LIS) type, but with a three-dimensional twist.

Space and Time Complexity

Time Complexity: O(n^2) where n is the number of cuboids (plus an O(n log n) sorting overhead, which is dominated by O(n^2) for n up to 100). Space Complexity: O(n) for the DP array.

Solution

The solution starts by sorting the dimensions of each cuboid so that the smallest dimension comes first and the largest (which will always be the height when placed optimally) comes last. After that, we sort the list of cuboids by their dimensions. We then use dynamic programming, where dp[i] represents the maximum stack height ending with the i-th cuboid in the sorted order. For each cuboid i, we check all previous cuboids j. If cuboid i can be stacked on top of cuboid j (i.e., every dimension of i is greater than or equal to the corresponding dimension of j), then we update dp[i] accordingly. Finally, the maximum value in our dp array is the answer.

Code Solutions

# Python solution for Maximum Height by Stacking Cuboids
def maxHeight(cuboids):
    n = len(cuboids)
    # Sort dimensions for each cuboid so that comparisons become easier
    for cuboid in cuboids:
        cuboid.sort()  # sorts in non-decreasing order

    # Sort all cuboids based on their dimensions
    cuboids.sort()
    
    # Initialize DP array; each dp[i] holds the max achievable height ending with cuboid i
    dp = [0] * n
    max_height = 0
    
    # Loop through each cuboid as the candidate top cuboid
    for i in range(n):
        # Use the height (largest dimension after sort) of the current cuboid
        dp[i] = cuboids[i][2]
        # Check all previous cuboids to see if this one can be placed on top
        for j in range(i):
            # If each dimension of cuboid i is >= corresponding dimension of cuboid j,
            # then cuboid i can be stacked on cuboid j.
            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])
        # Update overall maximum height
        max_height = max(max_height, dp[i])
    
    return max_height

# Example usage:
example = [[50,45,20],[95,37,53],[45,23,12]]
print(maxHeight(example))  # Expected output: 190
← Back to All Questions