Maximum height by stacking cuboids

Array Dynamic Programming Sorting

61.7% acceptance

Feb 25, 2026

1263

Given n cuboids with dimensions [width, length, height]. You can rotate any cuboid. Place cuboid i on cuboid j if all dimensions of i <= all dims of j (in some rotation). Return maximum stacked height.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_height(mut cuboids: Vec<Vec<i32>>) -> i32 {
    // Sort each cuboid's dimensions
    for c in &mut cuboids {
      c.sort_unstable();
    }
    // Sort cuboids by all dimensions
    cuboids.sort_unstable();
    let n = cuboids.len();
    // dp[i] = max height with cuboid i on top
    let mut dp: Vec<i32> = cuboids.iter().map(|c| c[2]).collect();
    let mut ans = *dp.iter().max().unwrap_or(&0);
    for i in 1..n {
      for j in 0..i {
        if cuboids[j][0] <= cuboids[i][0]
          && cuboids[j][1] <= cuboids[i][1]
          && cuboids[j][2] <= cuboids[i][2]
        {
          dp[i] = dp[i].max(dp[j] + cuboids[i][2]);
        }
      }
      ans = ans.max(dp[i]);
    }
    ans
  }
}