# Building Boxes
**Difficulty:** HARD
[External](https://leetcode.com/problems/building-boxes)
Canonical: https://scaleengineer.com/dsa/problems/building-boxes
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
---
## Problem
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._

**Example 1:**

![](https://assets.glich.co/dsa/building-boxes/image0.png)

**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.

**Example 2:**

![](https://assets.glich.co/dsa/building-boxes/image1.png)

**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.

**Example 3:**

![](https://assets.glich.co/dsa/building-boxes/image2.png)

**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.

**Constraints:**

* `1 <= n <= 109`

# Approaches
## Binary Search on the Answer
The problem asks for the minimum number of floor boxes. We can observe that if we can place `n` boxes with `k` boxes on the floor, we can certainly do so with `k+1` boxes (by just adding one more box on the floor). This monotonic relationship between the number of floor boxes and the maximum total boxes that can be placed allows us to binary search for the answer.

We can search for the minimum number of floor boxes, `k`, in the range `[1, n]`. For a given `k`, we need a function to calculate the maximum number of boxes we can place, let's call it `max_boxes(k)`. If `max_boxes(k) >= n`, it means `k` is a potential answer, and we try to find a smaller `k`. Otherwise, `k` is too small, and we need to increase it.
**Time:** O((log n)^2). The outer binary search for `k` runs `O(log n)` times. The inner `canPlace` function also performs a binary search for `i`. The range for `i` is roughly `sqrt(k)`, so the inner search takes `O(log(sqrt(k))) = O(log k)`. Since `k` can be up to `n`, the total time complexity is `O(log n * log n)`. · **Space:** O(1), as we only use a constant number of variables for calculations.
**Pros:** It's a standard problem-solving pattern (binary search the answer) that is robust.; Avoids complex mathematical formulas involving cube roots which might have precision issues.
**Cons:** Slower than the direct constructive approach.; The logic for calculating `max_boxes(k)` is non-trivial to derive and requires careful implementation.
### Explanation
To calculate `max_boxes(k)`, we must arrange the `k` floor boxes in the most efficient way to support stacks of boxes. The optimal arrangement is a pyramid built in a corner. The base of this pyramid is a triangle. 

First, we form the largest possible full triangular base of side `i` using `T(i) = i*(i+1)/2` boxes, where `T(i) <= k`. This base can support a complete pyramid (a tetrahedron) containing `C(i) = i*(i+1)*(i+2)/6` boxes in total. 

The remaining `j = k - T(i)` floor boxes are then arranged to start the next row of the base. These `j` boxes can themselves form the base of a 2D triangular stack, holding a total of `T(j) = j*(j+1)/2` boxes. Therefore, the total maximum boxes for `k` on the floor is `max_boxes(k) = C(i) + T(j)`.

The overall algorithm involves a binary search on `k`, and within it, another binary search to find the corresponding `i` for each `k`.

```java
class Solution {
    public int minimumBoxes(int n) {
        long low = 1, high = n;
        long ans = n;

        while (low <= high) {
            long k = low + (high - low) / 2;
            if (canPlace(k, n)) {
                ans = k;
                high = k - 1;
            } else {
                low = k + 1;
            }
        }
        return (int) ans;
    }

    // Checks if n boxes can be placed with k floor boxes
    private boolean canPlace(long k, int n) {
        // Find largest i such that i*(i+1)/2 <= k
        long i_low = 1, i_high = 45000; // A safe upper bound for i
        long i = 0;
        while(i_low <= i_high) {
            long mid = i_low + (i_high - i_low) / 2;
            long boxes_in_triangle = mid * (mid + 1) / 2;
            if (boxes_in_triangle <= k) {
                i = mid;
                i_low = mid + 1;
            } else {
                i_high = mid - 1;
            }
        }
        
        long basePyramidBoxes = i * (i + 1) * (i + 2) / 6;
        long remainingFloorBoxes = k - (i * (i + 1) / 2);
        long extraBoxes = remainingFloorBoxes * (remainingFloorBoxes + 1) / 2;
        
        long total_capacity = basePyramidBoxes + extraBoxes;
        // Check for overflow before comparison
        if (total_capacity < 0) return true; 
        return total_capacity >= n;
    }
}
```
### Algorithm
- The core idea is that the maximum number of boxes we can place, `max_boxes(k)`, is a monotonically increasing function of the number of boxes on the floor, `k`.
- This property allows us to use binary search on the answer `k`.
- We search for the smallest `k` in the range `[1, n]` such that `max_boxes(k) >= n`.
- The binary search proceeds as follows:
  1. Initialize `low = 1`, `high = n`, `ans = n`.
  2. While `low <= high`:
     a. Calculate `mid = k`.
     b. Check if `max_boxes(k) >= n` using a helper function.
     c. If it is, `k` is a possible answer, so we store it and try for a smaller `k`: `ans = k`, `high = k - 1`.
     d. If not, `k` is too small, so we need more floor boxes: `low = k + 1`.
- The helper function `max_boxes(k)` works by arranging the `k` floor boxes optimally:
  1. Find the largest integer `i` such that a triangle of side `i`, `T(i) = i*(i+1)/2`, uses at most `k` boxes. This `i` can be found with another binary search.
  2. These `T(i)` boxes support a full pyramid (tetrahedron) of `C(i) = i*(i+1)*(i+2)/6` boxes.
  3. The remaining `j = k - T(i)` floor boxes can support a 2D triangle of `T(j) = j*(j+1)/2` boxes.
  4. `max_boxes(k) = C(i) + T(j)`.

## Direct Mathematical Construction
Instead of searching for the answer, we can construct it directly by understanding the optimal placement of boxes. The most compact way to stack boxes under the given rules is to form a pyramid in a corner of the room. This structure is a tetrahedron. This approach calculates the answer by first filling the largest possible tetrahedron that fits within the `n` box limit, and then determining how many extra floor boxes are needed to place the remainder.
**Time:** O(log n). The first binary search for `i` runs on a range up to `(6n)^(1/3)`, taking `O(log(n^(1/3))) = O(log n)` time. The second binary search for `j` runs on a range up to `rem`, which is at most `O(n^(2/3))`, taking `O(log(n^(2/3))) = O(log n)` time. The total complexity is `O(log n)`. · **Space:** O(1), as only a few variables are needed for the calculation.
**Pros:** This is the most efficient approach, directly calculating the result without searching over a large range of possible answers.; It provides a deeper understanding of the problem's combinatorial structure.
**Cons:** The mathematical derivation of the optimal structure (pyramids and triangles) is more involved and less intuitive than a standard binary search approach.
### Explanation
A complete pyramid with a triangular base of side `i` contains a total of `C(i) = i*(i+1)*(i+2)/6` boxes. The number of boxes on its floor is `B(i) = i*(i+1)/2`.

First, we find the largest `i` such that `C(i) <= n`. This tells us the size of the biggest complete pyramid we can build. We can find this `i` using a binary search over a reasonable range (e.g., `1` to `2000`, since `C(2000)` exceeds `10^9`).

After building this pyramid, we have `rem = n - C(i)` boxes left to place. To place these `rem` boxes, we must add more boxes to the floor. Each new box on the floor allows more boxes to be stacked on top. If we add `j` boxes to the floor, we can place a total of `T(j) = j*(j+1)/2` additional boxes. So, we need to find the smallest `j` such that `T(j) >= rem`. This can also be found using a binary search.

The final answer is the sum of the floor boxes from the initial pyramid, `B(i)`, and the additional ones required for the remainder, `j`.

```java
class Solution {
    public int minimumBoxes(int n) {
        // Step 1: Find the largest i such that i*(i+1)*(i+2)/6 <= n
        long i = 0;
        long low = 1, high = 2000; // Safe upper bound for i, since C(2000) > 10^9
        while (low <= high) {
            long mid = low + (high - low) / 2;
            long total_boxes = mid * (mid + 1) * (mid + 2) / 6;
            if (total_boxes <= n) {
                i = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        long boxes_used = i * (i + 1) * (i + 2) / 6;
        long floor_boxes = i * (i + 1) / 2;
        long rem = n - boxes_used;

        if (rem == 0) {
            return (int) floor_boxes;
        }

        // Step 2: Find smallest j such that j*(j+1)/2 >= rem
        long j = 0;
        low = 1;
        high = rem; // j can be at most rem
        while (low <= high) {
            long mid = low + (high - low) / 2;
            long extra_capacity = mid * (mid + 1) / 2;
            if (extra_capacity >= rem) {
                j = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return (int) (floor_boxes + j);
    }
}
```
### Algorithm
- The optimal strategy is to build the largest complete pyramid (tetrahedron) that uses at most `n` boxes.
- Then, add the remaining boxes by expanding the base of the pyramid.
- The algorithm proceeds in two main steps:
  1. **Find the size of the largest complete pyramid**: Find the largest integer `i` such that the total boxes in a pyramid with base side `i`, `C(i) = i*(i+1)*(i+2)/6`, is less than or equal to `n`. This `i` can be found efficiently using binary search.
  2. **Place the remaining boxes**: 
     a. Calculate the boxes used in this pyramid, `C(i)`, and the number of boxes on its floor, `B(i) = i*(i+1)/2`.
     b. Calculate the remaining boxes to place: `rem = n - C(i)`.
     c. If `rem` is 0, the answer is `B(i)`.
     d. If `rem > 0`, we find the minimum number of additional floor boxes, `j`, required to place `rem` more boxes. The number of boxes that can be supported by `j` additional floor boxes is `T(j) = j*(j+1)/2`. We find the smallest `j` such that `T(j) >= rem`, again using binary search.
     e. The total minimum floor boxes is `B(i) + j`.

# Solutions
### Java

```java
class Solution {
public
  int minimumBoxes(int n) {
    int s = 0, k = 1;
    while (s + k * (k + 1) / 2 <= n) {
      s += k * (k + 1) / 2;
      ++k;
    }
    --k;
    int ans = k * (k + 1) / 2;
    k = 1;
    while (s < n) {
      ++ans;
      s += k;
      ++k;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumBoxes(int n) {
    int s = 0, k = 1;
    while (s + k * (k + 1) / 2 <= n) {
      s += k * (k + 1) / 2;
      ++k;
    }
    --k;
    int ans = k * (k + 1) / 2;
    k = 1;
    while (s < n) {
      ++ans;
      s += k;
      ++k;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumBoxes(self, n: int) -> int: s, k = 0, 1 while s + k * (k + 1) // 2 <= n: s += k * (k + 1) // 2 k += 1 k -= 1 ans = k * (k + 1) // 2 k = 1 while s < n: ans += 1 s += k k += 1 return ans

```