Solution: Building Boxes
Tags: algorithms, javascript, leetcode
Published: 2021-02-05 21:41:53

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/building-boxes/discuss/1035809/Easiest-Programmatic-Solution-or-beats-100-100).*

---

####[Leetcode Problem #1739 (*Hard*): Building Boxes](https://leetcode.com/problems/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.<br>These boxes are placed in the corner of the room,<br>where the corner is on the left side.
*Visual:*|![Example 1 Visual](https://assets.leetcode.com/uploads/2021/01/04/3-boxes.png)

Example 2:||
|---:|---|
*Input:*|n = 4
*Output:*|3
*Explanation:*|The figure above is for the placement of the four boxes.<br>These boxes are placed in the corner of the room,<br>where the corner is on the left side.
*Visual:*|![Example 2 Visual](https://assets.leetcode.com/uploads/2021/01/04/4-boxes.png)

Example 3:||
|---:|---|
*Input:*|n = 10
*Output:*|6
*Explanation:*|The figure above is for the placement of the ten boxes.<br>These boxes are placed in the corner of the room,<br>where the corner is on the back side.
*Visual:*|![Example 3 Visual](https://assets.leetcode.com/uploads/2021/01/04/10-boxes.png)


---

***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 **n**th triangular number is formed by finding the sum of the first **n** natural numbers, the **n**th tetrahedral number is formed by finding the sum of the first **n** triangular numbers. 

![image](https://assets.leetcode.com/users/images/db41e9d8-2916-47dc-94a6-e0eaae0e1cc5_1612558764.7190442.png)

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.

![image](https://assets.leetcode.com/users/images/9c850ca6-6f31-47c5-8f16-01db54a75d3c_1612561037.638008.png)


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:***
```javascript
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:***
```python
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
```