Problem

Given n cuboids where the dimensions of the ith cuboid is cuboids[i] = [widthi, lengthi, heighti] (0-indexed). Choose a subset of cuboids and place them on each other.

You can place cuboid i on cuboid j if widthi <= widthj and lengthi <= lengthj and heighti <= heightj. You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid.

Return the maximum height of the stacked cuboids.

Examples

Example 1:

Examples

Input:
cuboids = [ [50,45,20],[95,37,53],[45,23,12] ]
Output:
 190
Explanation:
Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.
Cuboid 0 is placed next with the 45x20 side facing down with height 50.
Cuboid 2 is placed next with the 23x12 side facing down with height 45.
The total height is 95 + 50 + 45 = 190.

Example 2:

Input:
cuboids = [ [38,25,45],[76,35,3] ]
Output:
 76
Explanation:
You can't place any of the cuboids on the other.
We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.

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:
After rearranging the cuboids, you can see that all cuboids have the same dimension.
You can place the 11x7 side down on all cuboids so their heights are 17.
The maximum height of stacked cuboids is 6 * 17 = 102.

Solution

Method 1 - Sorting and DP

There is something midleading here, you need to understand the differnece. If the question is: “You can place cuboid i on cuboid j if width[i] <= width[j] and length[i] <= length[j]” that’s will be difficult.

But it’s “You can place cuboid i on cuboid j if width[i] <= width[j] and length[i] <= length[j] and height[i] <= height[j]” That’s much easier.

Explanation

You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid. So for each cuboid, we sort its length in three dimension.

You can place cuboid i on cuboid j, we have width[i] <= width[j] and length[i] <= length[j] and height[i] <= height[j].

This condition will hold, after we sort each cuboid length, that is, small[i] <= small[j] and mid[i] <= mid[j] and big[i] <= big[j].

We apply a brute for double for loop, to compare each pair of cuboids, check if they satisfy the condition samll[i] <= small[j] and mid[i] <= mid[j] and big[i] <= big[j] If so, we can place cuboid i on cuboid j.

You may concern whether area[i] <= area[j]. Don’t worry, we always put the big[i] as the height, the area (width,length) = (small[i], mid[j]), and we have checked samll[i] <= small[j] && mid[i] <= mid[j].

Algo

  1. Sort the individual boxes, as any side can be length, width and height. Eg. cuboids = [ [50,45,20],[95,37,53],[45,23,12] ]. After sorting, cuboids = [ [20,45,50],[37,53,95],[12,23,45] ].
  2. Sort the cubes, by smaller property in descending order. If smaller property are equal, sort by 2nd property in descending order, and finally if 2nd property also equal, then sort by third property in descending order. For eg.cuboids = [37,53,95],[ [20,45,50],[12,23,45] ]
  3. Now, do LIS like logic. See the code below. dp[0] = 95; Now lets calculate dp[1]. cuboids[0][0] ≥ cuboids[1][0] && cuboids[0][1] ≥ cuboids[1][1] && cuboids[0][2] ≥ cuboids[1][2] ⇨ dp[1] = Math.max(dp[1], dp[0] + cuboids[j][2]) = dp[1] = 95 + 50 = 135. Similarly dp[2] = 135 + 45 = 190 as the if condition for checking previous cuboids matches.

Code

public int maxHeight(int[][] cuboids) {
	for (int[] a: cuboids) {
		Arrays.sort(a);
	}
	Arrays.sort(cuboids, (a, b) -> a[0] != b[0] ? b[0] - a[0] : (a[1] != b[1] ? b[1] - a[1] : b[2] - a[2]));
	int n = cuboids.length, ans = 0, dp[] = new int[n];
	for (int j = 0; j<n; ++j) {
		dp[j] = cuboids[j][2];
		for (int i = 0; i<j; ++i) {
			if (cuboids[i][0] >= cuboids[j][0] && cuboids[i][1] >= cuboids[j][1] && cuboids[i][2] >= cuboids[j][2]) {
				dp[j] = Math.max(dp[j], dp[i] + cuboids[j][2]);
			}
		}
		ans = Math.max(ans, dp[j]);
	}
	return res;
}

Complexity

  • Time: O(n) for first sorting + O(nlogn) for next sorting + O(n^2) = O(n^2)
  • Space: O(n)

Method 2 - Using Longest Increasing Subsequence

This is similar to Longest Increasing Subsequence LIS Problem, just validation we need to compare 3 dimensional. First we place the box at the height as the maximum, so all the box will be at the height position. Because the validation here is to check all 3 dimensional all non-decreasing, so we can use the same logic as LIS, for here, instead of just compare nums[i] >= num[j], we need to check 3 ways nums [length-i, width-i, height-i] >= nums[length-j, width-j, height-k].

Code

public int maxHeight(int[][] cuboids) {
	for (int[] cube : cuboids) Arrays.sort(cube);
	Arrays.sort(cuboids, (a, b) -> (a[0] + a[1] + a[2]) - (b[0] + b[1] + b[2]));
	int N = cuboids.length, res = 0;
	int[] dp = new int[N];
	for (int i = 0; i < N; i++) {
		dp[i] = cuboids[i][2];
		res = Math.max(res, dp[i]);
	}
	for (int i = 1; i < N; i++)
		for (int j = 0; j < i; j++)
			if (cuboids[j][0] <= cuboids[i][0] && 
				cuboids[j][1] <= cuboids[i][1] && 
				cuboids[j][2] <= cuboids[i][2]) {
				dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
				res = Math.max(res, dp[i]);
			}
	return res;
}

Complexity

  • Time: O(n)
  • Space: O(n)