Scale Engineer

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
Dynamic Programming
Algorithms
Sorting
Data structures
Array
Companies
Samsung

Prompt

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:

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

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:

  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.

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;    }}

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.

Solutions

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();  }}

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 →

Next problem