Building Boxes solution and explanation
4 more videos on this problem
LeetCode 1739. Building BoxesHappy Coding · 20:01 · 1K views
1739. Building Boxes (Leetcode Hard)Programming Live with Larry · 57:22 · 413 views
【每日一题】1739. Building Boxes, 1/26/2021Huifeng Guan · 29:01 · 324 views
Leetcode 1739. Building BoxesFearless Learner · 12:26 · 80 views
LeetCode 1739: Building BoxesAlitaCode · 28:11 · 13 views
The 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
xis placed on top of the boxy, then each side of the four vertical sides of the boxymust 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 <= 109
Approach overview
Problem 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 1: Iterative Build-Up of Layers
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.
def minimumBoxes(n):
def f(x):
return (x * (x + 1) * (x + 2)) // 6
lo, hi = 1, int(1e6)
while lo < hi:
mid = (lo + hi) // 2
if f(mid) >= n:
hi = mid
else:
lo = mid + 1
x = lo - 1
base = (x * (x + 1)) // 2
rest = n - f(x)
y = 0
while rest > 0:
y += 1
rest -= y
return base + y
n = 10
print(minimumBoxes(n)) # Output: 6#include <iostream>
#include <cmath>
long long minimumBoxes(long long n) {
auto f = [](long long x) { return x * (x + 1) * (x + 2) / 6; };
long long lo = 1, hi = 1e6;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (f(mid) >= n)
hi = mid;
else
lo = mid + 1;
}
long long x = lo - 1;
long long base = x * (x + 1) / 2;
long long rest = n - f(x);
long long y = 0;
while (rest > 0) {
y++;
rest -= y;
}
return base + y;
}
int main() {
long long n = 10;
std::cout << minimumBoxes(n) << std::endl; // Output: 6
return 0;
}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).
Approach 2: Mathematical Deduction and Direct Calculation
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.
class Solution {
public int minimumBoxes(int n) {
int lb = 0, base = 0, total = 0;
while (total < n) {
lb++;
base += lb;
total += base;
}
total -= base;
base -= lb;
while (total < n) {
base++;
total += base - lb;
}
return base;
}
public static void main(String[] args) {
Solution sol = new Solution();
int n = 10;
System.out.println(sol.minimumBoxes(n)); // Output: 6
}
}function minimumBoxes(n) {
let lb = 0, base = 0, total = 0;
while (total < n) {
lb++;
base += lb;
total += base;
}
total -= base;
base -= lb;
while (total < n) {
base++;
total += base - lb;
}
return base;
}
const n = 10;
console.log(minimumBoxes(n)); // Output: 6;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.
Time Complexity: O(sqrt(n)). Space Complexity: O(1) given direct formula computation for box placement and layer calculations.
Approach 3: Mathematical Rule
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).
func minimumBoxes(n int) int {
s, k := 0, 1
for s+k*(k+1)/2 <= n {
s += k * (k + 1) / 2
k++
}
k--
ans := k * (k + 1) / 2
k = 1
for s < n {
ans++
s += k
k++
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Build-Up of Layers | Time Complexity: |
| Mathematical Deduction and Direct Calculation | Time Complexity: |
| Mathematical Rule | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Building Boxes easy or hard?
Building Boxes is labeled Hard because the stacking constraint hides a mathematical pattern. Once you recognize the pyramid structure and derive the tetrahedral and triangular relationships, the implementation becomes short and efficient.
Building Boxes Python/Java solution
Python and C++ implementations often simulate the pyramid growth iteratively until the next layer would exceed n. Java and JavaScript solutions frequently use the mathematical formula with binary search to compute the pyramid height and then determine how many additional base boxes are required.
How to solve Building Boxes in O(log n)?
Use the tetrahedral formula k(k+1)(k+2)/6 to represent the number of boxes in a complete pyramid. Apply binary search to find the largest k such that this value does not exceed n. Compute the remaining boxes and extend the floor using triangular numbers until they are supported. The binary search step gives the O(log n) complexity.
What is the best approach for Building Boxes?
The most efficient approach uses mathematical deduction based on tetrahedral numbers. First find the largest full pyramid where k(k+1)(k+2)/6 ≤ n. Then place remaining boxes by expanding the triangular base using the smallest m where m(m+1)/2 ≥ remaining. This runs in O(log n) with binary search and O(1) space.
Is Building Boxes asked at Google/Amazon/Meta?
Building Boxes represents the type of mathematical reasoning and greedy construction problem commonly seen in interviews at companies like Google and Amazon. It tests pattern recognition, triangular number formulas, and the ability to translate geometric stacking constraints into math.
What data structure is used in Building Boxes?
No complex data structures are required. The solution relies on mathematical formulas such as triangular and tetrahedral numbers, along with greedy expansion of the base layer. Some implementations use binary search to compute the largest valid pyramid height efficiently.
What is the time complexity of Building Boxes?
The optimal solution runs in O(log n) time if binary search is used to determine the maximum full pyramid height. A simpler simulation approach that builds layers iteratively runs in about O(n^(1/3)) time because the pyramid height grows roughly with the cube root of n. Both approaches use constant O(1) extra space.