1739. Building Boxes LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1739. Building Boxes LeetCode Solution with the best time and space complexity. The solution to Building Boxes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Building Boxes solution in C++
Building Boxes solution in Java
Building Boxes solution in Python
Additional Resources

1739. Building Boxes LeetCode Solution image

Problem Statement of Building Boxes

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 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 <= 109

Complexity Analysis

Time Complexity: O(n^{1/3})
Space Complexity: O(1)

1739. Building Boxes LeetCode Solution in C++

class Solution {
 public:
  int minimumBoxes(int n) {
    int nBoxes = 0;
    int nextTouchings = 0;   // j
    int currLevelBoxes = 0;  // 1 + 2 + ... + j

    // Find the minimum j s.t. `nBoxes` = 1 + (1 + 2) + ... + (1 + 2 + ... + j)
    // >= n.
    while (nBoxes < n) {
      ++nextTouchings;
      currLevelBoxes += nextTouchings;
      nBoxes += currLevelBoxes;
    }

    // If nBoxes = n, the answer is `currLevelBoxes` = 1 + 2 + ... + j.
    if (nBoxes == n)
      return currLevelBoxes;

    // Otherwise, need to remove the boxes in the current level and rebuild it.
    nBoxes -= currLevelBoxes;
    currLevelBoxes -= nextTouchings;
    nextTouchings = 0;

    while (nBoxes < n) {
      ++nextTouchings;
      nBoxes += nextTouchings;
    }

    return currLevelBoxes + nextTouchings;
  }
};
/* code provided by PROGIEZ */

1739. Building Boxes LeetCode Solution in Java

class Solution {
  public int minimumBoxes(int n) {
    int nBoxes = 0;
    int nextTouchings = 0;  // j
    int currLevelBoxes = 0; // 1 + 2 + ... + j

    // Find the minimum j s.t. `nBoxes` = 1 + (1 + 2) + ... + (1 + 2 + ... + j)
    // >= n.
    while (nBoxes < n) {
      ++nextTouchings;
      currLevelBoxes += nextTouchings;
      nBoxes += currLevelBoxes;
    }

    // If nBoxes = n, the answer is `currLevelBoxes` = 1 + 2 + ... + j.
    if (nBoxes == n)
      return currLevelBoxes;

    // Otherwise, need to remove the boxes in the current level and rebuild it.
    nBoxes -= currLevelBoxes;
    currLevelBoxes -= nextTouchings;
    nextTouchings = 0;

    while (nBoxes < n) {
      ++nextTouchings;
      nBoxes += nextTouchings;
    }

    return currLevelBoxes + nextTouchings;
  }
}
// code provided by PROGIEZ

1739. Building Boxes LeetCode Solution in Python

class Solution:
  def minimumBoxes(self, n: int) -> int:
    nBoxes = 0
    nextTouchings = 0  # j
    currLevelBoxes = 0  # 1 + 2 + ... + j

    # Find the minimum j s.t. `nBoxes` = 1 + (1 + 2) + ... + (1 + 2 + ... + j)
    # >= n
    while nBoxes < n:
      nextTouchings += 1
      currLevelBoxes += nextTouchings
      nBoxes += currLevelBoxes

    # If nBoxes = n, the answer is `currLevelBoxes` = 1 + 2 + ... + j.
    if nBoxes == n:
      return currLevelBoxes

    # Otherwise, need to remove the boxes in the current level and rebuild it.
    nBoxes -= currLevelBoxes
    currLevelBoxes -= nextTouchings
    nextTouchings = 0

    while nBoxes < n:
      nextTouchings += 1
      nBoxes += nextTouchings

    return currLevelBoxes + nextTouchings
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents