Watch 6 video solutions for Building Boxes, a hard level problem involving Math, Binary Search, Greedy. This walkthrough by Happy Coding has 1,477 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
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:
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:
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 <= 109Problem Overview: You need to place n boxes in a room corner. A box can be placed on the floor or on top of another box only if all four vertical sides are supported. The goal is to minimize how many boxes touch the floor while still stacking all n boxes.
Approach 1: Iterative Build-Up of Layers (O(n^(1/3)) time, O(1) space)
The structure naturally forms a 3D pyramid in the corner. The bottom layer forms a triangular arrangement, the next layer sits on top of it, and so on. If the base side length is k, the number of boxes in a full pyramid equals the tetrahedral sum 1 + 3 + 6 + ... + k(k+1)/2. You iteratively keep adding layers while the total boxes used stays ≤ n. Once the largest full pyramid is built, some boxes remain. Add them greedily along the base edge, increasing the triangular base until the remaining boxes are supported.
This method simulates how the stack grows: increase the triangular base size, track the cumulative pyramid boxes, and stop when the next layer would exceed n. Then place the remaining boxes by expanding the base row one position at a time. The logic is simple and avoids heavy math, making it easy to implement during interviews.
Approach 2: Mathematical Deduction and Direct Calculation (O(log n) time, O(1) space)
The number of boxes in a complete pyramid of height k follows the tetrahedral formula k(k+1)(k+2)/6. Use binary search to find the largest k where this value is ≤ n. That determines the largest fully supported pyramid you can build. The floor boxes used so far equal the triangular number k(k+1)/2.
Let remaining = n - tetrahedral(k). These extra boxes must extend the base layer. Each additional base position increases support in a triangular progression: 1, 2, 3.... Find the smallest m such that m(m+1)/2 ≥ remaining. The final answer becomes base + m. This approach relies heavily on math patterns and a small greedy observation about how support grows along the floor.
Recommended for interviews: Start by describing the pyramid structure and show the iterative build-up idea. That demonstrates intuition about the stacking constraint. Strong candidates then compress the logic using tetrahedral formulas and greedy reasoning, optionally combined with binary search, which leads to the cleanest and fastest solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Build-Up of Layers | O(n^(1/3)) | O(1) | When deriving the pattern step-by-step or explaining the pyramid structure during interviews |
| Mathematical Deduction + Binary Search | O(log n) | O(1) | Optimal approach for large n using tetrahedral formulas and direct calculation |