Leetcode 1691. Maximum Height by Stacking Cuboids

Problem Explanation:

The problem provides us with the dimensions of n number of cuboids where each cuboid's dimension is mentioned as an integer array of [width, length and height]. The main task is to select some of these cuboids and stack them up so as to find the maximum height possible from the stacked cuboids.

However, there is a rule to stack this cuboid i.e., a cuboid i can only be placed on top of cuboid j if the dimensions of cuboid i i.e., width, length, and height are all less than or equal to the corresponding dimensions of cuboid j. There is a facility that we can manipulate a cuboid's dimensions by rotating it before placing it on top of another cuboid.

Your goal here is to return the maximum possible height that can be achieved by stacking the cuboids as per the rules.

The problem basically follows the principles of the Longest Increasing Subsequence (LIS) algorithm. The solution to this problem. We start by sorting the dimensions of each cuboid individually so that for each cuboid c[0] <= c[1] <= c[2]. Then we sort the whole set of cuboids.

We then create a dynamic programming array 'dp' and here dp[i] stores the maximum height by stacking the cuboids with cuboids[i] on the bottom.

We initialize dp[i] = cuboids[i][2] i.e., setting the maximum possible hight by placing cuboid i at the bottom-most/

Then we iterate over the cuboids and continuously update dp[i] according to the cuboids that can be stacked on top of i. Whenever we find cuboid j that satisfies the stacking conditions with cuboid i, dp[i] will take the maximum value between the current dp[i] and dp[j] + cuboids[i][2] (i.e; considering placing j on top of i).

The maximum possible height will then be the maximum height inside the dp array which we return by using max_element().

Let's now explain further and visually using an example and solution in different languages.

Python

1
2python
3from typing import List
4
5class Solution:
6    def maxHeight(self, cuboids: List[List[int]]) -> int:
7        cuboids = [[0,0,0]] + sorted(map(sorted, cuboids))    # Sort the boxes. Could put a few zeros at the start instead.
8        dp = [0] * len(cuboids)    # Initialize dp array
9        for i in range(1, len(cuboids)):    
10            for j in range(i):
11                if all(x >= y for x, y in zip(cuboids[i], cuboids[j])):    # Check if can put box i on box j
12                    dp[i] = max(dp[i], dp[j] + cuboids[i][2])    # Update the maximum possible height
13        return max(dp)    # Return the maximum height

Java

1
2java
3import java.util.Arrays;
4
5class Solution {
6    public int maxHeight(int[][] cuboids) {
7        
8    // Sort the dimensions of each cuboid such that smallest dimension is at index 0 and largest at index 2 in all cuboids.
9    for (int[] cuboid : cuboids) {
10        Arrays.sort(cuboid);
11    }
12        
13    // Sort all cuboids based on their dimensions.
14    Arrays.sort(cuboids, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
15        
16    int[] dp = new int[cuboids.length];
17    int max = 0;
18        
19    // Now iterate through all cuboids to calculate maximum height of stack.
20    for (int i = 0; i < cuboids.length; i++) {
21        dp[i] = cuboids[i][2];
22        for (int j = 0; j < i; j++) {
23            if (cuboids[i][0] >= cuboids[j][0] && cuboids[i][1] >= cuboids[j][1] && cuboids[i][2] >= cuboids[j][2]) {
24                dp[i] = Math.max(dp[i], cuboids[i][2] + dp[j]);
25            }
26        }
27        max = Math.max(max, dp[i]);
28    }
29        
30    return max;
31}
32}

JavaScript

1
2javascript
3var maxHeight = function(cuboids) {
4    for(let i = 0; i<cuboids.length; i++) {
5        // Sort the dimensions of each cuboid
6        cuboids[i].sort((a, b) => a-b);
7    }
8    cuboids.sort((a, b) => a[0] === b[0] ? (a[1] === b[1] ? a[2] - b[2] : a[1] - b[1]) : a[0] - b[0]);
9    let dp = new Array(cuboids.length).fill(0);
10    dp[0] = cuboids[0][2];
11    let ans = dp[0];
12    for(let i = 1; i<cuboids.length; i++) {
13        dp[i] = cuboids[i][2];
14        for(let j = 0; j < i; j++) {
15            if(cuboids[i][2] >= cuboids[j][2] &&
16               cuboids[i][0] >= cuboids[j][0] &&
17               cuboids[i][1] >= cuboids[j][1]) {
18                dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
19            }
20        }
21        ans = Math.max(ans, dp[i]);
22    }
23    return ans;
24};

C++

1
2c++
3class Solution {
4public:
5    int maxHeight(vector<vector<int>>& cuboids) {
6        for(auto& cuboid: cuboids)
7            sort(cuboid.begin(), cuboid.end()); // sort the dimensions of each cuboid
8        sort(cuboids.begin(), cuboids.end());
9        vector<int> m(cuboids.size(), 0);
10        int res = 0;
11        for(int i = 0; i < cuboids.size(); i++)
12        {
13            m[i] = cuboids[i][2]; // initial maximum height, according to the sort order
14            for(int j = 0; j < i; j++)
15                if(cuboids[i][0] >= cuboids[j][0] && cuboids[i][1] >= cuboids[j][1] && cuboids[i][2] >= cuboids[j][2])
16                    m[i] = max(m[i], m[j] + cuboids[i][2]);
17            res = max(res, m[i]);
18        }
19        return res;
20    }
21};

C#

1
2csharp
3public class Solution {
4    public int MaxHeight(int[][] cuboids) {
5        foreach (var cuboid in cuboids)
6            Array.Sort(cuboid);
7        Array.Sort(cuboids, (a, b) => a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
8        var dp = new int[cuboids.Length];
9        int max = 0;
10        for (int i = 0; i < cuboids.Length; i++) {
11            dp[i] = cuboids[i][2];
12            for (int j = 0; j < i; j++) {
13                if (cuboids[i][0] >= cuboids[j][0] && cuboids[i][1] >= cuboids[j][1] && cuboids[i][2] >= cuboids[j][2])
14                    dp[i] = Math.Max(dp[i], cuboids[i][2] + dp[j]);
15                }
16            max = Math.Max(max, dp[i]);
17        }
18        return max;
19    }
20}

Ruby

1
2ruby
3def max_height(cuboids)
4  cuboids.each { |cuboid| cuboid.sort!} # sort the dimensions of each cuboid
5  cuboids.sort!
6  dp = Array.new(cuboids.length, 0)
7  res = 0
8  for i in 0...cuboids.length
9    dp[i] = cuboids[i][2] # initial maximum height, according to the sort order
10    for j in 0...i
11      if cuboids[i][0] >= cuboids[j][0] && cuboids[i][1] >= cuboids[j][1] && cuboids[i][2] >= cuboids[j][2]
12        dp[i] = [dp[i], dp[j] + cuboids[i][2]].max
13      end
14    end
15    res = [res, dp[i]].max
16  end
17  res
18end
19

Swift

1
2swift
3class Solution {
4    func maxHeight(_ cuboids: [[Int]]) -> Int {
5        var sortedCuboids: [[Int]] = []
6        for cuboid in cuboids {
7            sortedCuboids.append(cuboid.sorted())
8        }
9        sortedCuboids.sort{ $0[0] != $1[0] ? $0[0] < $1[0] : $0[1] != $1[1] ? $0[1] < $1[1] : $0[2] < $1[2] }
10        var dp: [Int] = Array.init(repeating: 0, count: sortedCuboids.count)
11        var max_height = 0
12        for i in 0..<sortedCuboids.count {
13            dp[i] = sortedCuboids[i][2]
14            for j in 0..<i {
15                if sortedCuboids[i][0] >= sortedCuboids[j][0] && sortedCuboids[i][1] >= sortedCuboids[j][1] && sortedCuboids[i][2] >= sortedCuboids[j][2] {
16                    dp[i] = max(dp[i], dp[j] + sortedCuboids[i][2])
17                }
18            }
19            max_height = max(max_height, dp[i])
20        }
21        return max_height
22    }
23}

Kotlin

1
2kotlin
3fun maxHeight(cuboids: Array<IntArray>): Int {
4    cuboids.forEach { it.sort() }
5    cuboids.sortWith(compareBy<IntArray> { it[0] }.thenBy { it[1] }.thenBy { it[2] })
6    val dp = IntArray(cuboids.size)
7    var max = 0
8    for (i in cuboids.indices) {
9        dp[i] = cuboids[i][2]
10        for (j in 0 until i) {
11            if (cuboids[i][0] >= cuboids[j][0] && cuboids[i][1] >= cuboids[j][1] && cuboids[i][2] >= cuboids[j][2]) {
12                dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2])
13            }
14        }
15        max = Math.max(max, dp[i])
16    }
17    return max
18}

Conclusion

In conclusion, as you can see, the solution mainly involved the implementation of the hercules algorithm for Longest Increasing Subsequence (LIS). The key thing to remember here is that we need to sort each of the dimensions of the cuboid individually, and then again sort the overall cuboid. The reason for doing this is to ensure that when we are stacking the cuboids, we ensure that each subsequent cuboid is either the same size or larger dimensionally than the previous one.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫