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.
This approach builds upon understanding how to construct box towers incrementally. We know each layer can support more boxes as the arrangement expands upwards. By identifying the number of layers and how many boxes are placed in each, we can determine when to stop and how many boxes must touch the floor.
The code begins by using a helper function f that determines the maximum number of boxes that can be formed in a full layer structure for a given x value. Using binary search, it finds the largest x for which the exact or nearest potential full structure fits the number n.
Additional boxes that cannot fit into the existing complete pyramid structure are placed above the others. The sum of boxes touching the floor in layers is calculated, with extra required if leftover boxes exist.
Time Complexity: O(sqrt(n)) due to the binary search and layer calculation. Space Complexity: O(1).
This approach considers the mathematical build of layers directly deducing the solution using computed mathematical formulas. This reduces complexity by framing the entire building using known combinatorial mathematics to compute maximum structures for layers and add-ons precisely without excessive looping or conditional checks.
The solution begins with establishing base levels incrementally with layers, then adjusts a potential overfill condition by carefully allocating extra boxes on the top. Adjustments are calculated with sufficient ethics to minimize over each skyscrapering reduction. This avoids unnecessary computation.
Java
JavaScript
Time Complexity: O(sqrt(n)). Space Complexity: O(1) given direct formula computation for box placement and layer calculations.
According to the problem description, the box with the highest number of layers needs to be placed in the corner of the wall, and the arrangement of the boxes is in a step-like shape, which can minimize the number of boxes touching the ground.
Assume that the boxes are arranged in k layers. From top to bottom, if each layer is filled, then the number of boxes in each layer is 1, 1+2, 1+2+3, cdots, 1+2+cdots+k.
If there are still remaining boxes at this point, they can continue to be placed from the lowest layer. Assume that i boxes are placed, then the cumulative number of boxes that can be placed is 1+2+cdots+i.
The time complexity is O(\sqrt{n}), where n is the number of boxes given in the problem. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Build-Up of Layers | Time Complexity: |
| Mathematical Deduction and Direct Calculation | Time Complexity: |
| Mathematical Rule | — |
| 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 |
LeetCode 1739. Building Boxes • Happy Coding • 1,477 views views
Watch 5 more video solutions →Practice Building Boxes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor