Maximum Height by Stacking Cuboids

Hard
1059.

Maximum Height by Stacking Cuboids

Maximum Height by Stacking Cuboids is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} cuboids
 * @return {number}
 */
var maxHeight = function(cuboids) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Height by Stacking Cuboids — Problem & Solution

Maximum Height by Stacking Cuboids solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum Height by Stacking Cuboids is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google and Microsoft interviews.

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

Hints for Maximum Height by Stacking Cuboids

  1. Hint 1

    Sorting each cuboid's own dimensions ascending is always safe — and then the largest dimension should be the height.

  2. Hint 2

    After that normalisation, sort the cuboids and the problem becomes a longest-increasing-subsequence variant in three dimensions.

  3. Hint 3

    dp[i] = the tallest stack whose top cuboid is i.

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

  1. Sort each cuboid's [w, l, h] ascending in place.
  2. Sort the list of cuboids lexicographically.
  3. For each i, start dp[i] = boxes[i][2] and extend from every compatible earlier j.
  4. 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

Java

public static int maxHeight(int[][] cuboids) {
    int n = cuboids.length;
    int[][] boxes = new int[n][3];
    for (int i = 0; i < n; i++) {
        boxes[i] = cuboids[i].clone();
        Arrays.sort(boxes[i]);
    }
    Arrays.sort(boxes, (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];
    });
    int[] dp = new int[n];
    int best = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = boxes[i][2];
        for (int j = 0; j < i; j++) {
            if (boxes[j][0] <= boxes[i][0] && boxes[j][1] <= boxes[i][1] && boxes[j][2] <= boxes[i][2]) {
                dp[i] = Math.max(dp[i], dp[j] + boxes[i][2]);
            }
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}

C++

int maxHeight(vector<vector<int>>& cuboids) {
    vector<vector<int>> boxes = cuboids;
    for (auto& b : boxes) sort(b.begin(), b.end());
    sort(boxes.begin(), boxes.end());
    int n = (int) boxes.size();
    vector<int> dp(n, 0);
    int best = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = boxes[i][2];
        for (int j = 0; j < i; j++) {
            if (boxes[j][0] <= boxes[i][0] && boxes[j][1] <= boxes[i][1] && boxes[j][2] <= boxes[i][2]) {
                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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming