Box Stacking Problem Using Dynamic Programming in Java

Introduction

The Box Stacking Problem is a classic Dynamic Programming problem.

We are given three arrays:

height[]
width[]
length[]

Each index represents one type of box.

Our task is to find the maximum possible height of a stack by placing boxes one above another.

A box can be rotated, meaning any one of its three dimensions can be considered as its height.

A box can be placed on top of another box only when both dimensions of its base are strictly smaller than the base dimensions of the box below it.

Another important condition is that multiple instances of the same box can be used.

Problem Statement

Given:

height[i], width[i], length[i]

for n boxes, find the maximum possible height of the stack.

Conditions

A box can be rotated.
Any dimension can become the height.
Both base dimensions of the upper box must be strictly smaller than the corresponding dimensions of the lower box.
Multiple instances of the same box can be used.

Example

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

The maximum possible height is:

One possible stack has heights:

10 + 32 + 4 + 4 + 6 + 1 + 3 = 60

Understanding Box Rotation

For every box, there are three possible choices for the height.

Suppose a box has:

height = H
width  = W
length = L

We can create three orientations.

Rotation 1

Keep H as the height:

Height = H
Base = W × L

Rotation 2

Make W the height:

Height = W
Base = H × L

Rotation 3

Make L the height:

Height = L
Base = H × W

Therefore, n boxes produce:

3 × n

possible orientations.

Why Do We Normalize the Base?

Consider a base:

2 × 5

and another base:

5 × 2

They represent the same physical base.

Therefore, we store the larger dimension first:

max(base1, base2)

and the smaller dimension second:

min(base1, base2)

For example:

2 × 5

becomes:

5 × 2

This makes comparison easier.

Dynamic Programming Approach

After generating all rotations, we need to determine which boxes can be placed on top of which.

Suppose we have two orientations:

Box A:
Base = 10 × 8

Box B:
Base = 7 × 5

Since:

7 < 10
5 < 8

Box B can be placed on top of Box A.

Therefore:

A
↓
B

is a valid stack.

But if:

Box A = 10 × 8
Box B = 9 × 8

then Box B cannot be placed on A because:

9 < 10  → true
8 < 8   → false

The condition must be strictly smaller in both dimensions.

DP State

Let:

dp[i]

represent the maximum height of a stack where orientation i is the bottom box.

Initially:

dp[i] = boxes[i].height

because the box can form a stack by itself.

If another box j can be placed above box i, then:

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

The condition is:

boxes[j].width < boxes[i].width
AND
boxes[j].length < boxes[i].length

DP Transition

The main transition is:

if boxes[j].w < boxes[i].w
   && boxes[j].l < boxes[i].l

    dp[i] = max(dp[i],
                boxes[i].h + dp[j])

This means:

If box j can be placed on top of box i, add the best stack height starting from j to the height of i.

Finally:

answer = max(dp[i])

gives the maximum possible stack height.

Java Implementation

class Solution {

    static class Box {
        int h;
        int w;
        int l;

        Box(int h, int w, int l) {
            this.h = h;
            this.w = w;
            this.l = l;
        }
    }

    public int maxHeight(int[] height, int[] width, int[] length) {

        int n = height.length;

        // Each box has 3 possible orientations
        Box[] boxes = new Box[3 * n];

        int index = 0;

        for (int i = 0; i < n; i++) {

            // Rotation 1:
            // height = height[i]
            boxes[index++] = new Box(
                height[i],
                Math.max(width[i], length[i]),
                Math.min(width[i], length[i])
            );

            // Rotation 2:
            // height = width[i]
            boxes[index++] = new Box(
                width[i],
                Math.max(height[i], length[i]),
                Math.min(height[i], length[i])
            );

            // Rotation 3:
            // height = length[i]
            boxes[index++] = new Box(
                length[i],
                Math.max(height[i], width[i]),
                Math.min(height[i], width[i])
            );
        }

        int m = boxes.length;

        int[] dp = new int[m];

        // Initially, every box forms a stack by itself
        for (int i = 0; i < m; i++) {
            dp[i] = boxes[i].h;
        }

        int answer = 0;

        /*
         * Calculate maximum stack height.
         */
        for (int i = 0; i < m; i++) {

            for (int j = 0; j < m; j++) {

                /*
                 * Box j can be placed on top of box i
                 * if both base dimensions are smaller.
                 */
                if (boxes[j].w < boxes[i].w &&
                    boxes[j].l < boxes[i].l) {

                    dp[i] = Math.max(
                        dp[i],
                        boxes[i].h + dp[j]
                    );
                }
            }

            answer = Math.max(answer, dp[i]);
        }

        return answer;
    }
}

Step-by-Step Explanation of the Code

1. Create a Box Class

static class Box {
    int h;
    int w;
    int l;

    Box(int h, int w, int l) {
        this.h = h;
        this.w = w;
        this.l = l;
    }
}

Each orientation is represented using:

h → height
w → first base dimension
l → second base dimension

2. Generate Three Rotations

For every original box, we create three orientations.

First orientation

boxes[index++] = new Box(
    height[i],
    Math.max(width[i], length[i]),
    Math.min(width[i], length[i])
);

Here:

height = height[i]
base   = width[i] × length[i]

Second orientation

boxes[index++] = new Box(
    width[i],
    Math.max(height[i], length[i]),
    Math.min(height[i], length[i])
);

Here:

height = width[i]
base   = height[i] × length[i]

Third orientation

boxes[index++] = new Box(
    length[i],
    Math.max(height[i], width[i]),
    Math.min(height[i], width[i])
);

Here:

height = length[i]
base   = height[i] × width[i]

Therefore:

n boxes → 3n orientations

3. Initialize the DP Array

int[] dp = new int[m];

for (int i = 0; i < m; i++) {
    dp[i] = boxes[i].h;
}

Initially, every orientation is considered as a single box.

For example:

Box height = 10

Then:

dp[i] = 10

Later, if we can place other boxes above it, dp[i] will increase.

4. Check Whether One Box Can Be Placed on Another

if (boxes[j].w < boxes[i].w &&
    boxes[j].l < boxes[i].l)

This is the most important condition.

Suppose:

Bottom box = 10 × 8
Top box    = 7 × 5

Then:

7 < 10 → true
5 < 8  → true

So the top box can be placed on the bottom box.

5. Update the DP Value

dp[i] = Math.max(
    dp[i],
    boxes[i].h + dp[j]
);

Suppose:

Bottom box height = 10
Best stack above it = 20

Then:

Total = 10 + 20
      = 30

We keep the maximum value.

6. Find the Final Answer

answer = Math.max(answer, dp[i]);

Any orientation can become the bottom of the final stack.

Therefore, we check all dp[i] values.

The largest one is the answer.

Example Walkthrough

Consider:

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

For the fourth box:

H = 10
W = 12
L = 32

One orientation becomes:

Height = 10
Base = 32 × 12

Another orientation can have:

Height = 32
Base = 12 × 10

The algorithm generates all such possibilities.

It then checks which smaller bases can be placed above larger bases.

A valid stack can have heights:

Therefore:

10 + 32 + 4 + 4 + 6 + 1 + 3
= 60

So the result is:

Why Dynamic Programming Works

The problem has overlapping subproblems.

Suppose we already know the maximum height that can be stacked on top of a particular orientation.

When another larger box can use that orientation, we don't need to calculate the entire stack again.

We can reuse the previously calculated result:

dp[i] = current box height + best height above it

This is the main reason Dynamic Programming is suitable for this problem.

Important Points to Remember

1. Generate all rotations

Each box has three possible choices for its height.

3 × n orientations

2. Normalize base dimensions

Always store:

larger dimension first
smaller dimension second

using:

Math.max()
Math.min()

3. Use strict comparison

The upper box must satisfy:

upper.width < lower.width
upper.length < lower.length

Not:

<=

because equal dimensions are not allowed.

4. Multiple instances are allowed

The problem allows the same box type to be used multiple times.

The important observation is that every valid placement makes both base dimensions strictly smaller, so a valid stack keeps moving toward smaller bases.

Complexity Analysis

There are 3n orientations.

The DP compares orientations against each other.

Therefore:

Time Complexity

O((3n)²)

Since 3 is a constant:

O(n²)

Auxiliary Space

We store:

3n boxes

and:

dp[3n]

Therefore:

O(n)

Conclusion

The Box Stacking Problem can be solved efficiently using Dynamic Programming.

The main steps are:

Original boxes
      ↓
Generate 3 rotations
      ↓
Normalize base dimensions
      ↓
Check valid stacking conditions
      ↓
Calculate DP maximum heights
      ↓
Take maximum DP value

The most important idea is to transform the rotation problem into a collection of possible box orientations. Once that is done, the problem becomes a Dynamic Programming problem where we repeatedly find the best stack that can be placed on a particular base.

This approach gives:

Time Complexity  : O(n²)
Space Complexity : O(n)

and efficiently handles the given constraints.