LeetCode 1739 - Building Boxes

LeetCode Problem 1739

Difficulty: 🔴 Hard
Topics: Math, Binary Search, Greedy

Solution

Problem Understanding

The problem gives us n identical unit cubes that must be placed inside a cubic room. The goal is to minimize how many boxes directly touch the floor.

The placement rule is the important part of the problem. A box can only support another box on top of it if all four of its vertical sides are fully supported. Each side must either touch another box or a wall. This means floating or unstable stacks are not allowed.

The optimal structure naturally forms a corner pyramid. Since walls count as support, placing boxes in a corner is always best because the walls help satisfy the side-support condition. As we build upward, every higher layer must sit on a sufficiently large lower layer.

The input is a single integer n, representing both:

1. The dimensions of the room, which are large enough to hold all boxes.
2. The number of boxes that must be placed.

The output is the minimum number of boxes that must touch the floor.

The constraint 1 <= n <= 10^9 is extremely important. A brute-force simulation of placements is impossible. We need a mathematical or greedy observation that works in logarithmic or square-root scale time.

Several edge cases are important:

• Very small values like n = 1, where the answer is trivially 1.
• Values that exactly form a complete pyramid structure.
• Values that fall between two complete pyramid sizes.
• Very large values near 10^9, where inefficient iteration would time out.

Approaches

Brute Force Approach

A brute-force solution would attempt to simulate every possible valid placement of boxes and search for the arrangement with the fewest floor boxes.

One way to think about this is recursively placing boxes layer by layer while checking whether each supporting box satisfies the side-support rule. We could try all floor layouts and determine how many boxes can be stacked above them.

This approach is correct because it explores all valid configurations and eventually finds the minimum floor count.

However, it is computationally infeasible. Even for moderate n, the number of possible configurations grows explosively. Since n can be as large as 10^9, exhaustive search is completely impossible.

Optimal Greedy and Mathematical Approach

The key insight is that the densest valid structure is always a tetrahedral corner pyramid.

If the bottom layer forms a triangular arrangement:

1
1 1
1 1 1

then the next layer above can also form a smaller triangle, and so on.

The number of boxes in a complete pyramid of height h is:

$1+3+6+\cdots+\frac{h(h+1)}{2}=\frac{h(h+1)(h+2)}{6}$

The base layer contains:

$\frac{h(h+1)}{2}$

floor boxes.

The strategy is:

1. Build the largest complete pyramid possible.
2. If boxes remain, extend the bottom layer greedily with additional boxes.
3. Each additional floor box can support progressively more boxes above it.

This works because the pyramid arrangement maximizes vertical stacking efficiency.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all valid placements
Optimal	O(n^(1/3))	O(1)	Uses tetrahedral number properties

Algorithm Walkthrough

1. Start by building the largest complete pyramid possible.

A pyramid of height h contains:

$\frac{h(h+1)(h+2)}{6}$

boxes.

We repeatedly increase the height while the total number of boxes still fits within n. 2. Track the total boxes used and the number of floor boxes.

The floor of a pyramid with height h contains:

$\frac{h(h+1)}{2}$

boxes.

Once the largest complete pyramid is found, we know the current minimum floor usage for those boxes. 3. Compute how many boxes remain.

After constructing the maximal complete pyramid, there may still be some leftover boxes that must be placed. 4. Add extra floor boxes greedily.

Additional floor boxes are added in increasing order:

• The first extra floor box can support 1 additional box.
• The second can support 2.
• The third can support 3.

This forms another triangular growth pattern. 5. Continue adding floor boxes until all remaining boxes are covered.

We repeatedly subtract increasing counts from the remaining boxes until no boxes remain. 6. Return the total floor boxes.

Why it works

The corner pyramid is the densest valid arrangement because every upper layer requires a fully supported triangular layer beneath it. Complete triangular bases maximize how many boxes can be stacked above for a given number of floor boxes.

After the largest complete pyramid is built, the best way to place remaining boxes is to extend the floor minimally while preserving support conditions. Greedily adding floor boxes in increasing support capacity order achieves the smallest possible increase in floor usage.

Python Solution

class Solution:
    def minimumBoxes(self, n: int) -> int:
        total_boxes = 0
        height = 0

        # Build the largest complete pyramid
        while True:
            next_layer = (height + 1) * (height + 2) // 2

            if total_boxes + next_layer > n:
                break

            total_boxes += next_layer
            height += 1

        # Floor boxes in the complete pyramid
        floor_boxes = height * (height + 1) // 2

        remaining = n - total_boxes

        # Add extra floor boxes greedily
        extra = 0

        while remaining > 0:
            extra += 1
            remaining -= extra

        return floor_boxes + extra

The implementation directly follows the mathematical structure of the optimal arrangement.

The first loop builds the largest complete pyramid possible. Each iteration adds one more triangular layer. The variable next_layer represents how many boxes are needed to extend the pyramid by one level.

Once the loop stops, height represents the maximum fully completed pyramid height that fits within n.

The number of floor boxes for that pyramid is computed using the triangular number formula.

The remaining boxes are then handled greedily. Every additional floor box increases support capacity incrementally. The loop subtracts 1, then 2, then 3, and so on until all remaining boxes are accounted for.

Finally, the solution returns the original floor count plus the additional floor boxes required.

Go Solution

func minimumBoxes(n int) int {
    totalBoxes := 0
    height := 0

    // Build the largest complete pyramid
    for {
        nextLayer := (height + 1) * (height + 2) / 2

        if totalBoxes+nextLayer > n {
            break
        }

        totalBoxes += nextLayer
        height++
    }

    // Floor boxes in the complete pyramid
    floorBoxes := height * (height + 1) / 2

    remaining := n - totalBoxes

    // Add extra floor boxes greedily
    extra := 0

    for remaining > 0 {
        extra++
        remaining -= extra
    }

    return floorBoxes + extra
}

The Go implementation mirrors the Python logic almost exactly.

Since all calculations stay within integer range for n <= 10^9, standard int arithmetic is sufficient in Go.

Go uses explicit integer division with /, while Python uses //. No additional data structures are required, so the implementation remains compact and uses constant extra memory.

Worked Examples

Example 1

Input: n = 3

Step 1: Build complete pyramid

Height	Next Layer	Total Boxes
1	1	1
2	3	would become 4, stop

Largest complete pyramid height is 1.

Floor boxes:

1

Remaining boxes:

3 - 1 = 2

Step 2: Add extra floor boxes

Extra Floor Box	Remaining
1	1
2	-1

Total floor boxes:

1 + 2 = 3

Answer:

3

Example 2

Input: n = 4

Step 1: Build complete pyramid

Height	Next Layer	Total Boxes
1	1	1
2	3	4
3	6	would exceed, stop

Largest complete pyramid height is 2.

Floor boxes:

1 + 2 = 3

Remaining boxes:

4 - 4 = 0

No extra floor boxes needed.

Answer:

3

Example 3

Input: n = 10

Step 1: Build complete pyramid

Height	Next Layer	Total Boxes
1	1	1
2	3	4
3	6	10
4	10	would exceed

Largest complete pyramid height is 3.

Floor boxes:

1 + 2 + 3 = 6

Remaining boxes:

10 - 10 = 0

Answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^(1/3))	Pyramid height grows cubically
Space	O(1)	Only a few integer variables are used

The total number of boxes in a complete pyramid grows as:

$\frac{h(h+1)(h+2)}{6}\approx O(h^3)$

Therefore, the maximum pyramid height is approximately:

$h\approx O(n^{1/3})$

The second greedy loop grows roughly with triangular numbers, which is at most O(sqrt(n)), but in practice remains very small after the main pyramid construction.

The algorithm uses constant extra space because it stores only a fixed number of integer variables.

Test Cases

sol = Solution()

assert sol.minimumBoxes(1) == 1   # smallest possible input
assert sol.minimumBoxes(2) == 2   # cannot stack efficiently yet
assert sol.minimumBoxes(3) == 3   # example 1
assert sol.minimumBoxes(4) == 3   # example 2
assert sol.minimumBoxes(5) == 4   # requires one extra floor box
assert sol.minimumBoxes(6) == 5   # partial extension
assert sol.minimumBoxes(10) == 6  # example 3

assert sol.minimumBoxes(14) == 9  # exact next pyramid size
assert sol.minimumBoxes(15) == 9  # one extra box above complete pyramid
assert sol.minimumBoxes(20) == 10 # additional greedy extension

assert sol.minimumBoxes(100) == 34   # medium-sized case
assert sol.minimumBoxes(1000) == 161 # larger stress case

assert sol.minimumBoxes(10**9) > 0   # maximum constraint stress test

Test	Why
n = 1	Minimum boundary value
n = 2	Small non-stackable configuration
n = 3	Validates example 1
n = 4	Validates exact pyramid completion
n = 5	Tests leftover handling
n = 6	Tests continued greedy extension
n = 10	Validates example 3
n = 14	Exact tetrahedral number
n = 15	One above exact pyramid
n = 20	Larger partial extension
n = 100	Medium-sized correctness test
n = 1000	Larger stress scenario
n = 10^9	Maximum constraint performance test

Edge Cases

Exact Pyramid Sizes

Some values of n exactly equal a complete tetrahedral number. For example, n = 4 and n = 10 form perfect pyramids with no leftover boxes.

This can easily cause off-by-one bugs if the loop condition incorrectly stops too early or too late. The implementation handles this correctly by checking whether the next layer would exceed n before adding it.

Very Small Inputs

Inputs like n = 1 or n = 2 are important because the pyramid structure barely exists yet.

Naive implementations sometimes assume at least one complete higher layer can always be formed. This implementation correctly starts from height zero and incrementally builds upward, so tiny inputs work naturally.

Large Inputs Near 10^9

Large values can expose performance issues or integer overflow mistakes.

The implementation avoids recursion and avoids simulating actual box positions. Instead, it relies entirely on mathematical growth formulas, making it efficient even for the maximum input size.

Additionally, all intermediate values remain safely within integer limits for both Python and Go.