Box Stacking

Q: How do you identify the pattern for Box Stacking?

Look for key signals in the prompt: "stack" indicates The order matters: each box sits on the one below it, so the answer is a chain of boxes.; "both sides of its base strictly smaller" indicates A two-way rule, like nesting envelopes. Equal sides block the stack.; "maximum height" indicates A maximum of a sum: each box in the chain adds its height.; "a box can be turned" indicates Each box becomes three items, one for each face used as the base. Each item can be used at most once in one tower..

Hard·GeeksforGeeks Pro OnlyMedium

GeeksforGeeks

Problem Statement

You have n boxes. Each box has three sides: height, width and length. You can turn a box so that any one of its sides is the height. The other two sides then form its base.

Boxes can be stacked into a tower. A box can sit on another box only when both sides of its base are strictly smaller than the two sides of the base under it. Equal sides do not count. The same box may be used more than once in the tower, for example in two different turns.

Return the greatest height that a tower can reach.

Input

Three lists of length n: height, width and length. Box i has sides height[i], width[i] and length[i].

Output

The largest possible total height of a tower.

Example 1

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

Output: 60

From bottom to top the heights are 10, 32, 4, 4, 6, 1, 3. They add up to 60. Each base is strictly smaller on both sides than the base below it, and some boxes are used twice in different turns.

Example 2

Input: height = [1, 4, 3], width = [2, 5, 4], length = [3, 6, 1]

Output: 15

From bottom to top the heights are 4, 6, 1, 1, 3. They add up to 15, and each base is strictly smaller than the one under it on both sides.

Constraints

• 1 ≤ n ≤ 100
• 1 ≤ height[i], width[i], length[i] ≤ 10^6

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“stack”

→ The order matters: each box sits on the one below it, so the answer is a chain of boxes.

“both sides of its base strictly smaller”

→ A two-way rule, like nesting envelopes. Equal sides block the stack.

“maximum height”

→ A maximum of a sum: each box in the chain adds its height.

“a box can be turned”

→ Each box becomes three items, one for each face used as the base. Each item can be used at most once in one tower.

Approach Complexity Ladder

Brute Force — try every orientation that fits on topO(N · 2^(3N))O(N)

Recurse from the current top: each orientation whose base fits underneath is a choice; keep the tallest tower

Optimal — sort the orientations by base, then an O(N²) dpO(N²)O(N)

dp[i] = height[i] + the best dp[j] over earlier orientations with a strictly bigger base; sort the 3N orientations first

Brute Force Intuition

Make the 3N orientations. Start from the floor. For the current top, try every orientation whose base is strictly bigger on both sides, add its height, and continue from that orientation. The answer is the largest total over all these choices.

Recognition rule for this sub-pattern:

Sort by one dimension (ties broken carefully), then run LIS on the other.

Remember this · DP — Longest Increasing Subsequence

Trigger

Longest chain where each item must be bigger/fit inside the previous one (numbers, pairs, envelopes, words).

Think

Does each element extend the best chain ending at some smaller earlier element?

Key question

Sort first? Then what does "increasing" mean for these items?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Longest Increasing Subsequence translate into production architectures and low-level memory mechanics.

LLD Architecture