Maximum Height by Stacking Cuboids

Explore Other Solutions

Problem Description

So, you think stacking cuboids is as easy as stacking pancakes? Well, think again! The “Maximum Height by Stacking Cuboids” problem on LeetCode is here to remind you that life is not just about piling things up haphazardly. Imagine you have a bunch of cuboids (yes, those 3D rectangles that look like your childhood building blocks) and you want to stack them to reach the sky. But wait! You can only stack a cuboid on top of another if it fits perfectly.

In simpler terms, you need to find the maximum height you can achieve by stacking these cuboids, given that each cuboid can be rotated. So, if you thought you could just throw them on top of each other like a game of Jenga, think again! You need to sort them out first.

Code Solution


class Solution {
  public int maxHeight(int[][] cuboids) {
    for (int[] cuboid : cuboids)
      Arrays.sort(cuboid);

    Arrays.sort(cuboids, new Comparator() {
      @Override
      public int compare(int[] a, int[] b) {
        if (a[0] != b[0])
          return a[0] - b[0];
        if (a[1] != b[1])
          return a[1] - b[1];
        return a[2] - b[2];
      }
    });

    int[] dp = new int[cuboids.length];

    for (int i = 0; i < cuboids.length; ++i)
      dp[i] = cuboids[i][2];

    for (int i = 1; i < cuboids.length; ++i)
      for (int j = 0; j < i; ++j)
        if (cuboids[j][0] <= cuboids[i][0] && 
            cuboids[j][1] <= cuboids[i][1] && 
            cuboids[j][2] <= cuboids[i][2])
          dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);

    return Arrays.stream(dp).max().getAsInt();
  }
}

Approach Explanation

The approach taken in this solution is as follows:

Sorting: Each cuboid is sorted to ensure that the dimensions are in non-decreasing order. This makes it easier to compare and stack them.
Dynamic Programming: We use a dynamic programming array dp where dp[i] represents the maximum height achievable with the i-th cuboid at the bottom.
Comparison: For each cuboid, we check all previous cuboids to see if they can be stacked on top. If they can, we update the maximum height accordingly.

Time and Space Complexity

Time Complexity: O(n²), where n is the number of cuboids. This is due to the nested loops used to compare each cuboid with all previous ones.

Space Complexity: O(n) for the dp array used to store the maximum heights.

Real-World Example

Imagine you’re at a party, and you have a stack of boxes to impress your friends. You can only stack a box on another if it fits perfectly. If you try to stack a big box on a small one, you’ll end up with a disaster (and maybe a broken toe). This problem is just like that! You need to find the best way to stack your boxes (cuboids) to reach the highest point without causing a scene.