1739. Building Boxes
Asked at Adobe
Difficulty
Hard
Time
O(k) where k is the pyramid side
Space
O(1)
Pattern
Math
Companies
1
Problem
You have a cubic room whose width, length and height are all n units. You must place exactly n unit cubes inside it, following two rules.
First, every cube must rest on the floor or on top of another cube. Second, if a cube sits on top of another cube, then all four vertical sides of the lower cube must be blocked — each side must touch either a wall or another cube. In other words, a cube can only carry a cube above it when it is fully surrounded on all four sides.
Return the smallest number of cubes that can touch the floor in a valid arrangement of n cubes.
Cubes can only stack when fully surrounded
Constraints
- ●
1 <= n <= 10^9
Examples
n = 33n = 43n = 106Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Adobe | Hard | View all Adobe questions → |
How to Think About It
Brute force: for every candidate ground count, stack cubes upward and check capacity. Infeasible because n reaches 10^9 - you cannot simulate cube by cube. The answer must come from closed-form geometry.
Key insight: the most space-efficient building is a stair pyramid. A full pyramid whose base triangle has side s holds s(s+1)(s+2)/6 cubes total, of which s(s+1)/2 touch the ground.
First, binary search the largest s such that s(s+1)(s+2)/6 <= n. Those cubes are already supported. The leftover cubes must be added as a new bottom row extending the base triangle to side s+1.
The remainder rule: the j-th ground cube added to the extended triangle row brings j additional cube positions above it (itself plus j-1 stacked). Greedily accumulate 1, 2, 3, ... until the total added covers the remainder.
Check against known cases: n=3 gives s=2, total 3, remainder 0, answer 3; n=10 gives s=3, total 10, remainder 0, answer 6; n=4 gives s=2, total 4, remainder 0, answer 3.
Optimal Approach
A ground cube supports a whole stack, so the cheapest layout is a stair pyramid. Binary-search the largest s whose total volume s(s+1)(s+2)/6 is at most n, and record its ground count s(s+1)/2 plus used cubes. Then handle the remainder r: keep adding the next ground cube of the extended triangle row, where the j-th cube adds j more cube positions, until the accumulated total reaches r.
Walkthrough for n = 4:
- Try s=1: 123/6 = 1 <= 4. Try s=2: 234/6 = 4 <= 4. Try s=3: 3*4*5/6 = 10 > 4. So s=2.
- Used = 4, remainder = 0, ground so far = 2*3/2 = 3.
- Answer = 3.
Time: O(k) where k is the pyramid side, capped near 2000 for n <= 10^9 (effectively constant); space: O(1).
Stair pyramid plus a greedy remainder row
What Trips People Up in Real Interviews
Simulating cube by cube. With n up to a billion any loop touching each cube individually times out. The pyramid formulas compress everything into O(1)-class math.
Swapping the two formulas. The ground layer of a side-s triangle is s(s+1)/2; the full pyramid is s(s+1)(s+2)/6. Flipping them corrupts the binary search threshold and the final ground count.
Forgetting the second phase entirely. Finding the largest full pyramid is only half the problem - leftover cubes still demand new ground boxes. Skipping the greedy remainder step under-reports the answer.
Off-by-one in the binary search. You want the largest s whose pyramid fits (<= n). Use the seek-largest form mid = (lo + hi + 1) / 2 and move hi down when the candidate overflows.
Integer overflow in s(s+1)(s+2). The product reaches the 10^9 range, so compute in a 64-bit type (natural in Python, but C++ and Java need long) before dividing by 6.
Solution Code
O(k) where k is the pyramid side timedef minimumBoxes(n):
lo, hi = 0, 2000
while lo < hi:
mid = (lo + hi + 1) // 2
if mid * (mid + 1) * (mid + 2) // 6 <= n:
lo = mid
else:
hi = mid - 1
s = lo
total = s * (s + 1) * (s + 2) // 6
answer = s * (s + 1) // 2
remaining = n - total
added = 0
row = 0
while added < remaining:
row += 1
answer += 1
added += row
return answerFrequently Asked Questions
What is the Building Boxes problem?
With n unit cubes, build a house where every cube above the ground layer is supported by a cube directly beneath it, minimizing the number of cubes that touch the ground. This greedy-with-binary-search hard problem is a signature Adobe math question with n up to one billion.
How do you solve Building Boxes?
The optimal approach runs in O(k) where k is the pyramid side time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Building Boxes?
Building Boxes is asked at Adobe. It is a hard difficulty problem.
What are common mistakes on Building Boxes?
- Simulating cube by cube. With n up to a billion any loop touching each cube individually times out. The pyramid formulas compress everything into `O(1)`-class math.
- Swapping the two formulas. The ground layer of a side-s triangle is `s(s+1)/2`; the full pyramid is `s(s+1)(s+2)/6`. Flipping them corrupts the binary search threshold and the final ground count.
- Forgetting the second phase entirely. Finding the largest full pyramid is only half the problem - leftover cubes still demand new ground boxes. Skipping the greedy remainder step under-reports the answer.
- Off-by-one in the binary search. You want the largest s whose pyramid fits (`<= n`). Use the seek-largest form `mid = (lo + hi + 1) / 2` and move hi down when the candidate overflows.
- Integer overflow in `s(s+1)(s+2)`. The product reaches the 10^9 range, so compute in a 64-bit type (natural in Python, but C++ and Java need `long`) before dividing by 6.