Maximum Height by Stacking Cuboids — Hard Problem & Solution

cuboids[i] = [width, length, height]. You may rotate any cuboid freely, permuting its three dimensions however you like, and you may use any subset.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Sorting
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

cuboids[i] = [width, length, height]. You may rotate any cuboid freely, permuting its three dimensions however you like, and you may use any subset.

Cuboid j may sit on cuboid i only if width_i <= width_j, length_i <= length_j and height_i <= height_j after rotation. Return the maximum total height of a stack.

Example 1

Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]]
Output: 190
Explanation: All three stack once each is rotated to put its longest side vertical.

Example 2

Input: cuboids = [[38,25,45],[76,35,3]]
Output: 76
Explanation: Neither fits on the other, so take the taller one alone.

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: All six are the same box; every one stacks, giving 6 × 17.

Constraints

n == cuboids.length
1 <= n <= 100
1 <= width, length, height <= 100

How to solve Maximum Height by Stacking Cuboids

Two normalisations turn this into a weighted LIS. First sort each cuboid's three dimensions ascending, so the largest becomes the height. Then sort the cuboids lexicographically. Now dp[i] = height_i + max(dp[j]) over the earlier cuboids j whose three sorted dimensions are all no larger.

Approach

Sort each cuboid's [w, l, h] ascending in place.
Sort the list of cuboids lexicographically.
For each i, start dp[i] = boxes[i][2] and extend from every compatible earlier j.
Return the largest dp[i].

Why it works

The exchange argument behind the first sort is the crux: if a stack uses a cuboid with its largest side not vertical, rotating it so the largest side is vertical keeps the footprint no larger in both remaining dimensions and only increases the height — so the sorted orientation is never worse. That collapses six orientations per cuboid to one and makes the second sort meaningful, since a valid stack must then be non-decreasing in all three coordinates.

Complexity

Time — O(n²)
Space — O(n)

Pitfalls

Forgetting to sort each cuboid's own dimensions makes the comparison wrong in six ways at once.
The comparison is on all three dimensions, not just the footprint.
Equal dimensions are allowed, so identical cuboids all stack.

Reference solution

Python

from typing import List

def maxHeight(cuboids: List[List[int]]) -> int:
    boxes = sorted(sorted(c) for c in cuboids)
    n = len(boxes)
    dp = [0] * n
    best = 0
    for i in range(n):
        dp[i] = boxes[i][2]
        for j in range(i):
            if all(boxes[j][d] <= boxes[i][d] for d in range(3)):
                dp[i] = max(dp[i], dp[j] + boxes[i][2])
        best = max(best, dp[i])
    return best

JavaScript

var maxHeight = function(cuboids) {
    var boxes = [];
    for (var t = 0; t < cuboids.length; t++) {
        var c = cuboids[t].slice();
        c.sort(function(a, b) { return a - b; });
        boxes.push(c);
    }
    boxes.sort(function(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];
    });
    var n = boxes.length, dp = [], best = 0;
    for (var i = 0; i < n; i++) dp.push(0);
    for (i = 0; i < n; i++) {
        dp[i] = boxes[i][2];
        for (var j = 0; j < i; j++) {
            if (boxes[j][0] <= boxes[i][0] && boxes[j][1] <= boxes[i][1] && boxes[j][2] <= boxes[i][2]) {
                if (dp[j] + boxes[i][2] > dp[i]) dp[i] = dp[j] + boxes[i][2];
            }
        }
        if (dp[i] > best) best = dp[i];
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue