Building Boxes: Minimum Floor Boxes in a Corner Pyramid

You have a room shaped like a cuboid, with three walls forming a corner. You need to place n boxes in this corner. Every box must either sit directly on the floor or rest on top of another box (while also touching a wall or another box on two sides). Return the minimum number of boxes that touch the floor.

This is LeetCode 1739: Building Boxes, a hard problem that looks intimidating at first but becomes very clean once you recognize the geometric pattern. The boxes form a pyramid of triangular layers, and the math behind it boils down to triangular and tetrahedral numbers.

Why this problem matters

Building Boxes is a pure math and greedy problem disguised as 3D geometry. It teaches you to recognize closed-form summation formulas (triangular numbers, tetrahedral numbers) and to split a problem into "fill as much as you can optimally" followed by "handle the remainder greedily." That two-phase pattern, finding the largest complete structure and then incrementally adding the rest, appears in many math-flavored LeetCode problems.

Understanding how triangular numbers stack into tetrahedral numbers also builds intuition for combinatorial counting problems. When you see a quantity that grows as O(n^3), you should think about whether it decomposes into nested sums of triangular numbers. This problem gives you concrete practice with that decomposition.

The key insight: triangular layers form a tetrahedral pyramid

When you pack boxes into a corner, the bottom layer (layer 1) is a staircase triangle. Layer 1 can hold T(1) = 1 box on the floor. Layer 2, built on top of the first, holds T(2) = 3 boxes on its level. Layer k holds T(k) = k*(k+1)/2 boxes.

A complete pyramid of height h holds the sum of the first h triangular numbers. That sum has a nice closed form: h*(h+1)*(h+2)/6, the h-th tetrahedral number. The number of floor-touching boxes in a complete pyramid is 1 + 2 + 3 + ... + h = h*(h+1)/2.

So the algorithm has two phases:

1. Find the largest h where h*(h+1)*(h+2)/6 is at most n. This fills complete layers.
2. Add boxes to a partial next layer one at a time. The j-th floor box you add to the partial layer supports j total boxes above it (itself plus the j-1 boxes that can stack on top in the corner). Keep adding floor boxes until the total reaches or exceeds n.

The solution

def minimum_boxes(n: int) -> int:
    total = 0
    floor = 0
    layer = 0

    while total + (layer + 1) * (layer + 2) // 2 <= n:
        layer += 1
        floor += layer
        total += layer * (layer + 1) // 2

    extra = 1
    while total < n:
        total += extra
        floor += 1
        extra += 1

    return floor

How it works

The first while loop fills complete layers. At each iteration, it checks whether adding the next full triangular layer would still keep the total at or below n. If so, it adds that layer: floor increases by layer (the number of new floor boxes in that triangular layer), and total increases by T(layer) (the number of boxes that layer holds). After this loop, you have the largest complete pyramid that fits within n.

The second while loop handles the leftover. After the complete pyramid, there may be remaining boxes (n - total) that need to go into a partial next layer. Each new floor box at position extra in this partial layer supports extra boxes total (itself on the floor plus extra - 1 stacked above). So the first new floor box adds 1 to total, the second adds 2, the third adds 3, and so on. You keep adding floor boxes until total reaches or exceeds n.

The answer is the final value of floor, which counts all boxes touching the ground: both from the complete pyramid and from the partial layer.

Visual walkthrough

Complexity analysis

The cubic growth of tetrahedral numbers means even for n up to 10^9, the first loop runs about 1,000 iterations. This is extremely fast.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Triangular and tetrahedral number formulas

The triangular number T(k) = k*(k+1)/2 counts the sum 1 + 2 + ... + k. The tetrahedral number Te(h) = h*(h+1)*(h+2)/6 counts the sum of the first h triangular numbers. Recognizing when a problem reduces to these formulas lets you replace nested loops with constant-time arithmetic:

def triangular(k):
    return k * (k + 1) // 2

def tetrahedral(h):
    return h * (h + 1) * (h + 2) // 6

Problems like Arranging Coins, Perfect Squares, and other stacking or layering problems use these formulas. When you see quantities that grow quadratically or cubically, check whether triangular or tetrahedral numbers apply.

2. Greedy remainder after bulk fill

The pattern of filling as much as possible with a closed-form formula, then handling the leftover incrementally:

bulk = find_largest_complete_structure(n)
remaining = n - size(bulk)
while remaining > 0:
    add_one_unit()
    remaining -= contribution_of_unit()

This avoids iterating one unit at a time for the entire input. You jump ahead using math, then fine-tune with a small loop. The same approach works in problems like Arranging Coins (find the largest k where k*(k+1)/2 fits) and Bulb Switcher (recognize the square root pattern to skip iteration).

Edge cases

Before submitting, make sure your solution handles these:

• n = 1: one box on the floor, answer is 1. The first loop does not execute, the second loop adds one floor box.
• n = 3: a single complete triangular layer of side 2 does not fit (T(2) needs total = 4 via tetrahedral). Actually, h=1 gives total=1, then partial: 1+2=3 covers the rest. Floor = 1+2 = 3.
• n = 4: h=1 gives total=1, floor=1. Then partial adds j=1 (total=2), j=2 (total=4). Floor = 1+2 = 3.
• n = 10: exactly fills a complete pyramid of height 3. Te(3) = 3*4*5/6 = 10. Floor = T(3) = 6. No partial layer needed.
• Large n near 10^9: the loop still runs in about 1,000 iterations thanks to cubic growth, so there is no risk of timeout.
• n just above a tetrahedral number: for example n=11. Complete pyramid h=3 holds 10. Remaining = 1. One extra floor box covers it. Floor = 6+1 = 7.

From understanding to recall

You have read the two-phase solution and it makes sense. Find the largest complete tetrahedral pyramid, then greedily fill a partial layer. But can you reconstruct the loop conditions and the variable updates from scratch?

The details matter: using (layer + 1) * (layer + 2) // 2 as the look-ahead check in the first loop, incrementing floor by layer (not by 1), and using the incrementing extra counter in the second loop. These are small but specific, and getting any of them wrong produces a subtly incorrect answer.

Spaced repetition closes that gap. You practice writing the two-phase loop from scratch at increasing intervals. After a few rounds, you see "stacking in a corner" or "minimize floor-touching boxes" and the tetrahedral decomposition flows out automatically.

The greedy remainder pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Perfect Squares - Another math problem where recognizing a number-theoretic pattern replaces brute force
• Arranging Coins - Uses the same triangular number formula to find how many complete rows fit
• Bulb Switcher - A math problem where the answer is a closed-form formula, skipping simulation entirely

CodeBricks breaks the Building Boxes problem into its tetrahedral number recognition and greedy remainder building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a layered math question shows up in your interview, you do not think about it. You just write it.