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 <= 109In #1739 Building Boxes, boxes must be stacked in a corner so that each box above is supported by three boxes beneath it. The key observation is that the structure forms a 3D triangular pyramid. If we build complete layers, the total number of boxes follows the tetrahedral number formula k(k+1)(k+2)/6.
The strategy is to first find the largest number of complete layers k such that the tetrahedral count does not exceed n. These layers determine the minimum base boxes forming a triangular number k(k+1)/2. If boxes remain, we greedily extend the base by adding boxes along the edge, where each additional base box can support increasing stack heights (1, 2, 3, ...).
This approach avoids simulation and relies on mathematical patterns. Finding the largest valid layer count can be done iteratively or with binary search. The remaining boxes are handled using a greedy incremental process. Overall complexity is roughly O(n^{1/3}) or O(log n) depending on the layer search method, with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Mathematical layer expansion (greedy) | O(n^(1/3)) | O(1) |
| Binary search on pyramid height | O(log n) | O(1) |
Fireship
Use these hints if you're stuck. Try solving on your own first.
Suppose We can put m boxes on the floor, within all the ways to put the boxes, what’s the maximum number of boxes we can put in?
The first box should always start in the corner
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like Building Boxes are common in top tech interviews because they test mathematical reasoning and pattern recognition. Companies often expect candidates to combine math insights with greedy logic.
Yes. Binary search can be used to find the largest pyramid height whose tetrahedral box count is less than or equal to n. After that, a small greedy step handles the leftover boxes.
The optimal approach uses mathematical observations about tetrahedral numbers. First compute the maximum complete pyramid layers that fit within n boxes, then greedily add extra base boxes to support any remaining boxes.
A fully stacked corner pyramid forms a 3D triangular structure where each layer grows triangularly. The total number of boxes in such a structure follows the tetrahedral number formula k(k+1)(k+2)/6.