# Maximum Height by Stacking Cuboids 
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-height-by-stacking-cuboids)
Canonical: https://scaleengineer.com/dsa/problems/maximum-height-by-stacking-cuboids
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung)
---
## Problem
Given `n` `cuboids` where the dimensions of the `ith` cuboid is `cuboids[i] = [widthi, lengthi, heighti]` (**0-indexed**). Choose a **subset** of `cuboids` and place them on each other.

You can place cuboid `i` on cuboid `j` if `widthi <= widthj` and `lengthi <= lengthj` and `heighti <= heightj`. You can rearrange any cuboid's dimensions by rotating it to put it on another cuboid.

Return _the **maximum height** of the stacked_ `cuboids`.

**Example 1:**

**![](https://assets.glich.co/dsa/maximum-height-by-stacking-cuboids/image0.jpg)**

**Input:** cuboids = [[50,45,20],[95,37,53],[45,23,12]]
**Output:** 190
**Explanation:**
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
**Explanation:**
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
**Explanation:**
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`

# Approaches
## Dynamic Programming on All Rotations
This approach guarantees finding the optimal solution by considering all possible valid orientations for each cuboid. The core idea is to transform the problem into a variation of the Longest Increasing Subsequence (LIS) problem. We generate every possible way a cuboid can be oriented, creating a larger list of potential building blocks for our stack. Then, we use dynamic programming to find the sequence of these blocks that can be stacked on top of each other and results in the maximum total height.
**Time:** O(n^2). Generating candidates takes O(n). Sorting `3n` candidates takes O(n log n). The nested loops for the dynamic programming part take O((3n)^2) = O(n^2). Thus, the overall time complexity is dominated by the DP calculation. · **Space:** O(n), where n is the number of cuboids. We store `3n` candidates and a `dp` array of size `3n`, which simplifies to O(n).
**Pros:** This approach is guaranteed to be correct as it explores all valid stacking configurations.; It correctly models the problem as a longest path in a DAG, which has a standard DP solution.
**Cons:** The state space for the DP is larger (`3n` instead of `n`), leading to a higher constant factor in time complexity compared to simpler heuristics.; The implementation is more complex as it requires generating and managing orientations for each cuboid.
### Explanation
To solve this problem correctly, we must account for the fact that any cuboid can be rotated. A cuboid with dimensions `(d1, d2, d3)` can be oriented in three distinct ways by choosing each dimension as the height. For consistency, we can order the base dimensions (width and length). This gives us three candidate orientations for each cuboid:

1.  Height `d1`, Base `(min(d2, d3), max(d2, d3))`. Cuboid: `[min(d2, d3), max(d2, d3), d1]`
2.  Height `d2`, Base `(min(d1, d3), max(d1, d3))`. Cuboid: `[min(d1, d3), max(d1, d3), d2]`
3.  Height `d3`, Base `(min(d1, d2), max(d1, d2))`. Cuboid: `[min(d1, d2), max(d1, d2), d3]`

We generate these three orientations for each of the `n` input cuboids, creating a list of `3n` candidates. The problem then becomes finding the highest stack using a subset of these candidates, with the constraint that we can only use one orientation from each original cuboid.

A crucial insight is that if we have a valid stack, we cannot use two different orientations of the same original cuboid. This is because for one orientation `o1` to be stacked on another `o2` from the same original cuboid, their dimensions `(w, l, h)` must be non-decreasing. Since they are permutations of the same set of dimensions, this is only possible if they are identical, which would violate the 'subset' rule if we disallow stacking identical items from the same source.

This simplifies the problem to finding the longest path in a Directed Acyclic Graph (DAG), where nodes are the `3n` candidates and an edge exists from `j` to `i` if candidate `j` can be placed under `i`. The weight of the path is the sum of heights. This is a classic LIS-type problem solvable with dynamic programming.

```java
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    // A helper class to store candidate cuboid orientations
    static class CuboidCandidate {
        int w, l, h, originalIndex;

        public CuboidCandidate(int w, int l, int h, int originalIndex) {
            this.w = w;
            this.l = l;
            this.h = h;
            this.originalIndex = originalIndex;
        }
    }

    public int maxHeight(int[][] cuboids) {
        ArrayList<CuboidCandidate> candidates = new ArrayList<>();
        for (int i = 0; i < cuboids.length; i++) {
            int[] c = cuboids[i];
            // Orientation 1
            candidates.add(new CuboidCandidate(Math.min(c[0], c[1]), Math.max(c[0], c[1]), c[2], i));
            // Orientation 2
            candidates.add(new CuboidCandidate(Math.min(c[0], c[2]), Math.max(c[0], c[2]), c[1], i));
            // Orientation 3
            candidates.add(new CuboidCandidate(Math.min(c[1], c[2]), Math.max(c[1], c[2]), c[0], i));
        }

        // Sort candidates to enable DP
        Collections.sort(candidates, (a, b) -> {
            if (a.w != b.w) return Integer.compare(a.w, b.w);
            if (a.l != b.l) return Integer.compare(a.l, b.l);
            return Integer.compare(a.h, b.h);
        });

        int n = candidates.size();
        int[] dp = new int[n];
        int maxHeight = 0;

        for (int i = 0; i < n; i++) {
            dp[i] = candidates.get(i).h; // Base case: stack of one
            for (int j = 0; j < i; j++) {
                CuboidCandidate current = candidates.get(i);
                CuboidCandidate prev = candidates.get(j);

                // Check if we can stack current on top of prev
                if (prev.originalIndex != current.originalIndex &&
                    prev.w <= current.w &&
                    prev.l <= current.l &&
                    prev.h <= current.h) {
                    dp[i] = Math.max(dp[i], current.h + dp[j]);
                }
            }
            maxHeight = Math.max(maxHeight, dp[i]);
        }

        return maxHeight;
    }
}
```
### Algorithm
*   For each of the `n` cuboids, generate all 3 possible unique orientations. To make comparisons standard, for each orientation, represent its base dimensions `(width, length)` such that `width <= length`.
*   This results in a list of up to `3n` candidate cuboids. Each candidate should store its dimensions `(w, l, h)` and the index of the original cuboid it came from.
*   Sort this list of `3n` candidates. A good sorting order is lexicographically by `(w, l, h)`.
*   Initialize a dynamic programming array, `dp`, of size `3n`. `dp[i]` will store the maximum height of a stack that has candidate `i` at the very top.
*   Iterate through the sorted candidates from `i = 0` to `3n-1`:
    *   Initialize `dp[i]` to the height of candidate `i`, `h_i`. This represents a stack consisting of only this single cuboid.
    *   Iterate through all previous candidates `j` from `0` to `i-1`.
    *   Check if candidate `j` can be placed under candidate `i`. This requires two conditions:
        1.  They must originate from different cuboids: `original_index_j != original_index_i`.
        2.  The dimensions must be non-decreasing: `w_j <= w_i`, `l_j <= l_i`, and `h_j <= h_i`.
    *   If candidate `j` can be placed under `i`, it means we can potentially form a taller stack. Update `dp[i] = max(dp[i], h_i + dp[j])`.
*   The final answer is the maximum value found in the `dp` array, which represents the maximum height achievable across all possible valid stacks.

## Dynamic Programming with a Greedy Heuristic
A simpler and faster, but potentially incorrect, approach is to use a greedy heuristic. The heuristic is to decide on a fixed orientation for each cuboid before attempting to stack them. A natural greedy choice is to orient each cuboid such that its largest dimension is its height, as this maximizes the height contribution of each individual cuboid. After fixing the orientation for all cuboids, the problem reduces to finding the longest increasing subsequence on these `n` fixed cuboids, which can be solved with dynamic programming.
**Time:** O(n^2). Sorting the `n` cuboids takes O(n log n). The DP calculation involves a nested loop, taking O(n^2) time. The total complexity is O(n^2). · **Space:** O(n) for the `dp` array.
**Pros:** Simpler to understand and implement than the fully correct solution.; Faster in practice due to a smaller DP state space (`n` vs `3n`), resulting in smaller constant factors in its time complexity.
**Cons:** The core greedy assumption is flawed. Always choosing the largest dimension as the height is not always optimal. A smaller height might allow a cuboid to be placed on a wider variety of other cuboids, or enable a larger cuboid to be placed on top of it, leading to a greater total height.; This approach will fail on certain test cases where the optimal solution requires using a smaller dimension as a height for some cuboids in the stack.
### Explanation
This method simplifies the problem by making a greedy choice upfront. For each cuboid, we sort its three dimensions `d1 <= d2 <= d3`. We then treat this as a fixed cuboid with width `d1`, length `d2`, and height `d3`. This assumes that to maximize the total height, we should always use the largest possible dimension of each cuboid as its height.

Once we have this list of `n` 'canonical' cuboids, we sort them. Then, we apply a standard dynamic programming algorithm similar to finding the Longest Increasing Subsequence. Let `dp[i]` be the maximum height of a stack ending with cuboid `i`. We compute `dp[i]` by trying to place it on top of any preceding cuboid `j` that fits underneath it.

While this approach works for the given examples, it is not guaranteed to be correct. The initial greedy choice might prevent finding the true optimal solution. For instance, using a smaller height for a cuboid creates a larger base, which might be necessary to support a different, very tall cuboid that couldn't be placed otherwise.

```java
import java.util.Arrays;

class Solution {
    public int maxHeight(int[][] cuboids) {
        // Step 1: Create canonical representation for each cuboid
        for (int[] cuboid : cuboids) {
            Arrays.sort(cuboid);
        }

        // Step 2: Sort all cuboids
        Arrays.sort(cuboids, (a, b) -> {
            if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
            if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
            return Integer.compare(a[2], b[2]);
        });

        // Step 3: Dynamic Programming (LIS)
        int n = cuboids.length;
        int[] dp = new int[n];
        int maxHeight = 0;

        for (int i = 0; i < n; i++) {
            dp[i] = cuboids[i][2]; // Height of the current cuboid
            for (int j = 0; j < i; j++) {
                // Check if cuboid j can be placed under cuboid i
                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], cuboids[i][2] + dp[j]);
                }
            }
            maxHeight = Math.max(maxHeight, dp[i]);
        }

        return maxHeight;
    }
}
```
### Algorithm
*   For each cuboid, create a canonical representation by sorting its dimensions, e.g., `[d1, d2, d3]` becomes `[w, l, h]` where `w <= l <= h`. This greedily assumes the largest dimension should always be the height.
*   You now have a list of `n` canonical cuboids.
*   Sort this list of `n` cuboids, for example, lexicographically based on their `(w, l, h)` dimensions.
*   Initialize a `dp` array of size `n`, where `dp[i]` stores the maximum height of a stack ending with cuboid `i`.
*   Iterate from `i = 0` to `n-1`:
    *   Set `dp[i] = h_i` as the base case.
    *   Iterate from `j = 0` to `i-1`.
    *   If cuboid `j` can be placed under cuboid `i` (i.e., `w_j <= w_i`, `l_j <= l_i`, `h_j <= h_i`), update `dp[i] = max(dp[i], h_i + dp[j])`.
*   The answer is the maximum value in the `dp` array.

# Solutions
### Java

```java
class Solution {
public
  int maxHeight(int[][] cuboids) {
    for (var c : cuboids) {
      Arrays.sort(c);
    }
    Arrays.sort(cuboids, (a, b)->a[0] == b[0]
                             ? (a[1] == b[1] ? a[2] - b[2] : a[1] - b[1])
                             : a[0] - b[0]);
    int n = cuboids.length;
    int[] f = new int[n];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
          f[i] = Math.max(f[i], f[j]);
        }
      }
      f[i] += cuboids[i][2];
    }
    return Arrays.stream(f).max().getAsInt();
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} cuboids * @return {number} */ var maxHeight =
  function (cuboids) {
    for (const c of cuboids) {
      c.sort((a, b) => a - b);
    }
    cuboids.sort((a, 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];
    });
    const n = cuboids.length;
    const f = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
      for (let j = 0; j < i; ++j) {
        const ok =
          cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2];
        if (ok) f[i] = Math.max(f[i], f[j]);
      }
      f[i] += cuboids[i][2];
    }
    return Math.max(...f);
  };

```

### CPP

```cpp
class Solution {
public:
  int maxHeight(vector<vector<int>> &cuboids) {
    for (auto &c : cuboids)
      sort(c.begin(), c.end());
    sort(cuboids.begin(), cuboids.end());
    int n = cuboids.size();
    vector<int> f(n);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
          f[i] = max(f[i], f[j]);
        }
      }
      f[i] += cuboids[i][2];
    }
    return *max_element(f.begin(), f.end());
  }
};

```

### Python

```python
class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int: for c in cuboids: c . sort() cuboids . sort() n = len(cuboids) f = [0] * n  # f[i] meaning level-i as the base layer/level 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 ] # not inside if block, eg input [[38,25,45],[76,35,3]] return max ( f ) ############ # in python3, range() is the same as xrange() in python2 class Solution : def maxHeight ( self , cuboids : List [ List [ int ]]) -> int : """ :type cuboids: List[List[int]] :rtype: int """ for cuboid in cuboids : cuboid . sort () cuboids . append ([ 0 , 0 , 0 ]) cuboids . sort () dp = [ 0 ] * len ( cuboids ) for i in range ( 1 , len ( cuboids )): for j in range ( i ): if all ( cuboids [ j ][ k ] <= cuboids [ i ][ k ] for k in range ( 3 )): dp [ i ] = max ( dp [ i ], dp [ j ] + cuboids [ i ][ 2 ]) return max ( dp )

```