LeetCode 1691 - Maximum Height by Stacking Cuboids

This problem gives us a collection of 3D cuboids, where each cuboid is represented by three dimensions: width, length, a

leetcodehardarraydynamic-programmingsorting

LeetCode Problem 1691

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Sorting

Solution

LeetCode 1691 - Maximum Height by Stacking Cuboids

Problem Understanding

This problem gives us a collection of 3D cuboids, where each cuboid is represented by three dimensions: width, length, and height. We may choose any subset of these cuboids and stack them vertically to maximize the total height.

A cuboid can be placed on top of another cuboid only if all three of its dimensions are less than or equal to the corresponding dimensions of the cuboid below it. The important detail is that every cuboid may be rotated freely. Since a cuboid has three dimensions, we may rearrange them in any order before stacking.

The task is to determine the maximum possible total height obtainable by stacking valid cuboids.

The input is a list of cuboids:

cuboids[i] = [widthi, lengthi, heighti]

The output is a single integer representing the tallest achievable stack.

The constraints are relatively small:

  • Number of cuboids, n <= 100
  • Each dimension is at most 100

These limits strongly suggest that an O(n²) dynamic programming solution is acceptable. Exponential approaches become infeasible because every cuboid may or may not be included, and each cuboid also has multiple orientations.

Several edge cases are important:

  • A single cuboid, where the answer is simply its maximum possible height after rotation.
  • Cuboids that cannot stack together at all.
  • Multiple cuboids with identical dimensions.
  • Cases where rotating a cuboid is necessary to achieve the optimal answer.
  • Chains where a locally taller cuboid is not globally optimal.

The problem guarantees all dimensions are positive integers, so we never need to handle zero or negative sizes.

Approaches

Brute Force Approach

A brute force solution would try every possible subset of cuboids and every possible ordering and orientation of those cuboids.

For each cuboid, there are up to 6 possible rotations. If we consider all subsets, all permutations, and all orientations, the search space becomes enormous.

The brute force algorithm would:

  1. Generate every orientation for every cuboid.
  2. Try every ordering of cuboids.
  3. Validate whether the stack is legal.
  4. Compute the total height.
  5. Track the maximum.

This guarantees correctness because every valid stack is explored. However, the complexity becomes factorial and exponential, making it completely impractical even for n = 100.

Key Insight

The critical observation is that rotation freedom allows us to normalize each cuboid.

If we sort the three dimensions of a cuboid:

[a, b, c] where a <= b <= c

then we can always treat c as the height and a, b as the base dimensions.

Why does this work?

Because if a cuboid can be rotated arbitrarily, then sorting dimensions guarantees a canonical orientation that is never worse than any other orientation for stacking purposes.

After normalizing every cuboid individually, we can sort the entire list of cuboids lexicographically. Then the problem becomes extremely similar to the Longest Increasing Subsequence problem.

We define:

dp[i] = maximum stack height ending with cuboid i on top

For every pair (j, i) where j < i, if cuboid j can support cuboid i, then:

dp[i] = max(dp[i], dp[j] + height[i])

This reduces the problem to a clean O(n²) dynamic programming solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential / factorial Exponential Tries all subsets, rotations, and permutations
Optimal Dynamic Programming O(n²) O(n) Sort cuboids and apply LIS-style DP

Algorithm Walkthrough

  1. Normalize every cuboid by sorting its three dimensions.

For example:

[50, 45, 20] -> [20, 45, 50]

This guarantees a consistent orientation for every cuboid. 2. Sort the entire cuboid list lexicographically.

After sorting, smaller cuboids naturally appear before larger ones. This simplifies transition logic because when processing cuboid i, all potential lower cuboids already appear earlier in the array. 3. Create a DP array.

dp[i]

represents the maximum achievable stack height with cuboid i at the top. 4. Initialize each state.

At minimum, a stack containing only cuboid i has height:

dp[i] = cuboids[i][2]

because the largest dimension is treated as height. 5. Compare every earlier cuboid.

For each i, iterate through all j < i.

If:

cuboids[j][0] <= cuboids[i][0]
cuboids[j][1] <= cuboids[i][1]
cuboids[j][2] <= cuboids[i][2]

then cuboid j can be placed below cuboid i. 6. Update the DP transition.

If stacking is valid:

dp[i] = max(dp[i], dp[j] + cuboids[i][2])
  1. Return the largest value in the DP array.

That value represents the tallest achievable stack.

Why it works

Sorting each cuboid internally guarantees a canonical orientation that preserves all valid stacking possibilities. Sorting the entire cuboid list ensures that when processing cuboid i, every possible predecessor appears earlier in the array.

The DP recurrence correctly computes the best stack ending at each cuboid because every valid previous cuboid is considered exactly once. Since every stack must end at some cuboid, the maximum DP value is the optimal answer.

Python Solution

from typing import List

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        # Normalize each cuboid by sorting dimensions
        for cuboid in cuboids:
            cuboid.sort()

        # Sort all cuboids lexicographically
        cuboids.sort()

        n = len(cuboids)

        # dp[i] = maximum stack height with cuboid i on top
        dp = [0] * n

        max_height = 0

        for i in range(n):
            dp[i] = cuboids[i][2]

            for j in range(i):
                if (
                    cuboids[j][0] <= cuboids[i][0]
                    and cuboids[j][1] <= cuboids[i][1]
                    and cuboids[j][2] <= cuboids[i][2]
                ):
                    dp[i] = max(dp[i], dp[j] + cuboids[i][2])

            max_height = max(max_height, dp[i])

        return max_height

The implementation begins by sorting the dimensions inside every cuboid. This step handles rotation implicitly and converts every cuboid into a standard form.

Next, the entire list of cuboids is sorted lexicographically. This ordering guarantees that smaller cuboids appear before larger compatible cuboids.

The dynamic programming array stores the best stack height ending at each cuboid. Initially, every cuboid forms a stack of height equal to its own height.

The nested loop checks all previous cuboids. If a previous cuboid fits beneath the current cuboid, the DP transition attempts to extend the stack.

Finally, the largest value across all DP states is returned.

Go Solution

package main

import "sort"

func maxHeight(cuboids [][]int) int {
	// Normalize dimensions inside each cuboid
	for _, cuboid := range cuboids {
		sort.Ints(cuboid)
	}

	// Sort all cuboids lexicographically
	sort.Slice(cuboids, func(i, j int) bool {
		for k := 0; k < 3; k++ {
			if cuboids[i][k] != cuboids[j][k] {
				return cuboids[i][k] < cuboids[j][k]
			}
		}
		return false
	})

	n := len(cuboids)

	dp := make([]int, n)

	maxHeight := 0

	for i := 0; i < n; i++ {
		dp[i] = cuboids[i][2]

		for j := 0; j < i; j++ {
			if cuboids[j][0] <= cuboids[i][0] &&
				cuboids[j][1] <= cuboids[i][1] &&
				cuboids[j][2] <= cuboids[i][2] {

				if dp[j]+cuboids[i][2] > dp[i] {
					dp[i] = dp[j] + cuboids[i][2]
				}
			}
		}

		if dp[i] > maxHeight {
			maxHeight = dp[i]
		}
	}

	return maxHeight
}

The Go implementation follows the same logic as the Python solution. The main difference is the use of sort.Slice for lexicographical sorting.

Go slices are reference types, so sorting individual cuboids modifies them in place. Integer overflow is not a concern because the maximum possible height is at most:

100 cuboids * 100 height = 10000

which easily fits inside Go's int.

Worked Examples

Example 1

Input:

[[50,45,20],[95,37,53],[45,23,12]]

Step 1: Normalize Cuboids

Original Sorted
[50,45,20] [20,45,50]
[95,37,53] [37,53,95]
[45,23,12] [12,23,45]

Step 2: Sort Entire List

[
    [12,23,45],
    [20,45,50],
    [37,53,95]
]

Step 3: DP Computation

i Cuboid Initial dp[i] Transitions Final dp[i]
0 [12,23,45] 45 none 45
1 [20,45,50] 50 45 + 50 95
2 [37,53,95] 95 95 + 95 190

Answer:

190

Example 2

Input:

[[38,25,45],[76,35,3]]

Step 1: Normalize

Original Sorted
[38,25,45] [25,38,45]
[76,35,3] [3,35,76]

Step 2: Sort

[
    [3,35,76],
    [25,38,45]
]

Step 3: DP

i Cuboid dp[i]
0 [3,35,76] 76
1 [25,38,45] 45

The second cuboid cannot support the first because 76 > 45.

Answer:

76

Example 3

Input:

[[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]

Step 1: Normalize

Every cuboid becomes:

[7,11,17]

Step 2: Sort

The array remains six identical cuboids.

Step 3: DP

i dp[i]
0 17
1 34
2 51
3 68
4 85
5 102

Answer:

102

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Nested DP transitions across all cuboid pairs
Space O(n) DP array stores one value per cuboid

The preprocessing steps are relatively cheap. Sorting dimensions inside each cuboid costs constant time because there are only three values. Sorting the cuboid list costs O(n log n).

The dominant cost comes from the double loop used for dynamic programming, which performs O(n²) comparisons. Since n <= 100, this is easily efficient enough.

Test Cases

from typing import List

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        for cuboid in cuboids:
            cuboid.sort()

        cuboids.sort()

        n = len(cuboids)
        dp = [0] * n

        answer = 0

        for i in range(n):
            dp[i] = cuboids[i][2]

            for j in range(i):
                if (
                    cuboids[j][0] <= cuboids[i][0]
                    and cuboids[j][1] <= cuboids[i][1]
                    and cuboids[j][2] <= cuboids[i][2]
                ):
                    dp[i] = max(dp[i], dp[j] + cuboids[i][2])

            answer = max(answer, dp[i])

        return answer

sol = Solution()

assert sol.maxHeight([[50,45,20],[95,37,53],[45,23,12]]) == 190
# provided example 1

assert sol.maxHeight([[38,25,45],[76,35,3]]) == 76
# provided example 2

assert sol.maxHeight([
    [7,11,17],
    [7,17,11],
    [11,7,17],
    [11,17,7],
    [17,7,11],
    [17,11,7]
]) == 102
# provided example 3

assert sol.maxHeight([[1,1,1]]) == 1
# single cuboid

assert sol.maxHeight([[1,2,3],[3,4,5]]) == 8
# simple valid stacking chain

assert sol.maxHeight([[4,5,6],[1,2,3],[2,3,4]]) == 13
# multiple cuboids stack in order

assert sol.maxHeight([[10,10,1],[1,1,10]]) == 20
# rotation required for optimal stacking

assert sol.maxHeight([[100,100,100],[100,100,100]]) == 200
# identical large cuboids

assert sol.maxHeight([[5,5,5],[4,4,4],[3,3,3],[2,2,2]]) == 14
# descending chain

assert sol.maxHeight([[1,2,100],[3,4,5]]) == 100
# tallest single cuboid better than stacking

Test Summary

Test Why
Example 1 Validates standard stacking chain
Example 2 Validates non-stackable cuboids
Example 3 Validates identical normalized cuboids
Single cuboid Smallest input size
Simple stacking chain Basic DP transition correctness
Multiple stack order Validates sorting behavior
Rotation required Ensures dimension normalization works
Identical large cuboids Ensures equal dimensions are stackable
Descending chain Validates long LIS-style stacking
Tallest single cuboid Ensures algorithm does not force stacking

Edge Cases

Single Cuboid

When only one cuboid exists, there are no stacking decisions to make. A buggy implementation might incorrectly initialize DP values or assume at least one transition exists.

This implementation handles the case naturally because each dp[i] starts as the cuboid's own height. The answer becomes that single value.

Cuboids That Cannot Stack

Some inputs contain cuboids where no pair satisfies the dimension constraints. In these cases, the correct answer is simply the tallest individual cuboid after rotation.

The implementation handles this because DP transitions occur only when all three dimensions satisfy the stacking condition. Otherwise, the cuboid remains an independent stack.

Multiple Identical Cuboids

Equal dimensions are allowed because the condition uses <=, not <.

A common mistake is accidentally enforcing strict inequality, which would incorrectly reject valid stacks of identical cuboids.

This solution explicitly uses <= comparisons, so identical cuboids stack correctly.

Rotation-Dependent Solutions

Some optimal stacks are only possible after rotating cuboids. A naive implementation that preserves the original orientation may miss valid stacks entirely.

Sorting each cuboid's dimensions guarantees every cuboid is considered in its best canonical orientation for stacking, eliminating orientation-related bugs.