Solution: Building Boxes

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #1739 (Hard): Building Boxes

---

Description:

You have a cubic storeroom where the width, length, and height of the room are all equal to n units. You are asked to place n boxes in this room where each box is a cube of unit side length. There are however some rules to placing the boxes:

• You can place the boxes anywhere on the floor.
• If box x is placed on top of the box y, then each side of the four vertical sides of the box y must either be adjacent to another box or to a wall.

Given an integer n, return the minimum possible number of boxes touching the floor.

---

Examples:

Example 1:
Input:	n = 3
Output:	3
Explanation:	The figure above is for the placement of the three boxes. These boxes are placed in the corner of the room, where the corner is on the left side.
Visual:

Example 2:
Input:	n = 4
Output:	3
Explanation:	The figure above is for the placement of the four boxes. These boxes are placed in the corner of the room, where the corner is on the left side.
Visual:

Example 3:
Input:	n = 10
Output:	6
Explanation:	The figure above is for the placement of the ten boxes. These boxes are placed in the corner of the room, where the corner is on the back side.
Visual:

---

Constraints:

• 1 <= n <= 10^9

---

Idea:

This is an extremely simple problem once we realize that the ideal shapes formed by the instructions are tetrahedral numbers.

Tetrahedral numbers are a subset of Pascal's triangle. Where the nth triangular number is formed by finding the sum of the first n natural numbers, the nth tetrahedral number is formed by finding the sum of the first n triangular numbers.

In this sense, height represents the progression of natural numbers, bottom represents the progression of triangular numbers, and total represents the progression of tetrahedral numbers. This makes it extremely easy to calculate tetrahedral numbers iteratively.

So this means we can first build tetrahedral numbers programmatically by adding successive triangular numbers until we go past N. From each idea tetrahedral number, removing one from the base will mean having to remove a whole vertical strip of boxes that rely on that one.

Then we can narrow in on the final answer by working backwards through the natural numbers that make up the final triangular number in our tetrahedral number until we go below N again.

Since we've now narrowed it down to just under what we need, we should add 1 back to our bottom and return the answer.

---

Javascript Code:

var minimumBoxes = function(N) {
    let height = total = bottom = 1
    while (total < N) height++, bottom += height, total += bottom
    while (total >= N) bottom--, total -= height, height--
    return bottom + 1
};

---

Python Code:

class Solution(object):
    def minimumBoxes(self, N):
        height, bottom, total = 1, 1, 1
        while total < N:
            height += 1
            bottom += height
            total += bottom
        while total >= N:
            bottom -= 1
            total -= height
            height -= 1
        return bottom + 1