Box Stacking

Problem Overview

Any side of a box can be its height, and a box may sit on another only when both base sides are strictly smaller.

Intuition

Any side of a box can be its height, and a box may sit on another only when both base sides are strictly smaller. Generating the three rotations and sorting them by base length turns the search into a weighted increasing subsequence: each rotation extends the best earlier rotation that can support it.

Algorithm

1For each box, create three rotations and store the base so width is at most length.
2Sort rotations by length descending.
3Let dp[i] start as the height of rotation i.
4For every earlier rotation j, if both of its base sides are strictly larger, set dp[i] to the max of dp[i] and dp[j] plus the height of i.
5Return the largest dp value.

Example Walkthrough

Input: height = [4,1,4,10], width = [6,2,5,12], length = [7,3,6,32]

1. Each box contributes three possible bases.
2. A decreasing chain of bases can place several rotations in one stack.
3. The tallest such chain has height 60.

Output: 60

Common Pitfalls

• Both base sides must be strictly smaller. A larger area is not enough.
• Equal bases cannot stack, so one copy of a rotation is enough.
• Sort by one base side so a valid support always appears earlier in the list.
• The answer is the tallest dp value, not the sum of every rotation.

Box Stacking.java

Java

// Approach: Any side may be the height, so each box becomes three rotations
// with the base ordered so width <= length. A repeated base cannot be stacked
// on itself, so one copy of each rotation is enough. Sort by length descending
// and let dp[i] be the tallest stack with rotation i on top: it extends any
// earlier rotation whose width and length are both strictly larger.
// Complexity: O(n^2) time, O(n) extra space.
import java.util.*;

class Solution {
    public int maxHeight(int[] height, int[] width, int[] length) {
        int n = height.length;
        int[][] boxes = new int[3 * n][3];
        int m = 0;
        for (int i = 0; i < n; i++) {
            m = add(boxes, m, width[i], length[i], height[i]);
            m = add(boxes, m, height[i], length[i], width[i]);
            m = add(boxes, m, height[i], width[i], length[i]);
        }

        Arrays.sort(boxes, 0, m, (a, b) -> Integer.compare(b[1], a[1]));

        int[] dp = new int[m];
        int ans = 0;
        for (int i = 0; i < m; 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])
                    dp[i] = Math.max(dp[i], dp[j] + boxes[i][2]);
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    // Store [width, length, height] with width <= length.
    private int add(int[][] boxes, int m, int w, int l, int h) {
        if (w > l) {
            int t = w;
            w = l;
            l = t;
        }
        boxes[m][0] = w;
        boxes[m][1] = l;
        boxes[m][2] = h;
        return m + 1;
    }
}

Was this solution helpful?