Maximum Height by Stacking Cuboids

Hard

#1551Time: 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).1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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.

Example 1:

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 <= width_i, length_i, height_i <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

Height d1, Base (min(d2, d3), max(d2, d3)). Cuboid: [min(d2, d3), max(d2, d3), d1]
Height d2, Base (min(d1, d3), max(d1, d3)). Cuboid: [min(d1, d3), max(d1, d3), d2]
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.

1import java.util.Arrays;2import java.util.ArrayList;3import java.util.Collections;4 5class Solution {6    // A helper class to store candidate cuboid orientations7    static class CuboidCandidate {8        int w, l, h, originalIndex;9 10        public CuboidCandidate(int w, int l, int h, int originalIndex) {11            this.w = w;12            this.l = l;13            this.h = h;14            this.originalIndex = originalIndex;15        }16    }17 18    public int maxHeight(int[][] cuboids) {19        ArrayList<CuboidCandidate> candidates = new ArrayList<>();20        for (int i = 0; i < cuboids.length; i++) {21            int[] c = cuboids[i];22            // Orientation 123            candidates.add(new CuboidCandidate(Math.min(c[0], c[1]), Math.max(c[0], c[1]), c[2], i));24            // Orientation 225            candidates.add(new CuboidCandidate(Math.min(c[0], c[2]), Math.max(c[0], c[2]), c[1], i));26            // Orientation 327            candidates.add(new CuboidCandidate(Math.min(c[1], c[2]), Math.max(c[1], c[2]), c[0], i));28        }29 30        // Sort candidates to enable DP31        Collections.sort(candidates, (a, b) -> {32            if (a.w != b.w) return Integer.compare(a.w, b.w);33            if (a.l != b.l) return Integer.compare(a.l, b.l);34            return Integer.compare(a.h, b.h);35        });36 37        int n = candidates.size();38        int[] dp = new int[n];39        int maxHeight = 0;40 41        for (int i = 0; i < n; i++) {42            dp[i] = candidates.get(i).h; // Base case: stack of one43            for (int j = 0; j < i; j++) {44                CuboidCandidate current = candidates.get(i);45                CuboidCandidate prev = candidates.get(j);46 47                // Check if we can stack current on top of prev48                if (prev.originalIndex != current.originalIndex &&49                    prev.w <= current.w &&50                    prev.l <= current.l &&51                    prev.h <= current.h) {52                    dp[i] = Math.max(dp[i], current.h + dp[j]);53                }54            }55            maxHeight = Math.max(maxHeight, dp[i]);56        }57 58        return maxHeight;59    }60}

Complexity

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).

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2 3class Solution {4    public int maxHeight(int[][] cuboids) {5        // Step 1: Create canonical representation for each cuboid6        for (int[] cuboid : cuboids) {7            Arrays.sort(cuboid);8        }9 10        // Step 2: Sort all cuboids11        Arrays.sort(cuboids, (a, b) -> {12            if (a[0] != b[0]) return Integer.compare(a[0], b[0]);13            if (a[1] != b[1]) return Integer.compare(a[1], b[1]);14            return Integer.compare(a[2], b[2]);15        });16 17        // Step 3: Dynamic Programming (LIS)18        int n = cuboids.length;19        int[] dp = new int[n];20        int maxHeight = 0;21 22        for (int i = 0; i < n; i++) {23            dp[i] = cuboids[i][2]; // Height of the current cuboid24            for (int j = 0; j < i; j++) {25                // Check if cuboid j can be placed under cuboid i26                if (cuboids[j][0] <= cuboids[i][0] &&27                    cuboids[j][1] <= cuboids[i][1] &&28                    cuboids[j][2] <= cuboids[i][2]) {29                    dp[i] = Math.max(dp[i], cuboids[i][2] + dp[j]);30                }31            }32            maxHeight = Math.max(maxHeight, dp[i]);33        }34 35        return maxHeight;36    }37}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int maxHeight(int[][] cuboids) {4    for (var c : cuboids) {5      Arrays.sort(c);6    }7    Arrays.sort(cuboids, (a, b)->a[0] == b[0]8                             ? (a[1] == b[1] ? a[2] - b[2] : a[1] - b[1])9                             : a[0] - b[0]);10    int n = cuboids.length;11    int[] f = new int[n];12    for (int i = 0; i < n; ++i) {13      for (int j = 0; j < i; ++j) {14        if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {15          f[i] = Math.max(f[i], f[j]);16        }17      }18      f[i] += cuboids[i][2];19    }20    return Arrays.stream(f).max().getAsInt();21  }22}

1/** * @param {number[][]} cuboids * @return {number} */ var maxHeight =2  function (cuboids) {3    for (const c of cuboids) {4      c.sort((a, b) => a - b);5    }6    cuboids.sort((a, b) => {7      if (a[0] != b[0]) return a[0] - b[0];8      if (a[1] != b[1]) return a[1] - b[1];9      return a[2] - b[2];10    });11    const n = cuboids.length;12    const f = new Array(n).fill(0);13    for (let i = 0; i < n; ++i) {14      for (let j = 0; j < i; ++j) {15        const ok =16          cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2];17        if (ok) f[i] = Math.max(f[i], f[j]);18      }19      f[i] += cuboids[i][2];20    }21    return Math.max(...f);22  };

1class Solution {2public:3  int maxHeight(vector<vector<int>> &cuboids) {4    for (auto &c : cuboids)5      sort(c.begin(), c.end());6    sort(cuboids.begin(), cuboids.end());7    int n = cuboids.size();8    vector<int> f(n);9    for (int i = 0; i < n; ++i) {10      for (int j = 0; j < i; ++j) {11        if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {12          f[i] = max(f[i], f[j]);13        }14      }15      f[i] += cuboids[i][2];16    }17    return *max_element(f.begin(), f.end());18  }19};

1class Solution:2    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 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem