Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach - 1
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Approach - 2
3.1.
Steps of Algorithm 
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Box Stacking

Author Harsh Goyal
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

This blog will discuss the various approaches to solve the box stacking problem. Before jumping into the approach of stacking the box problem, let’s first understand the problem.

Also Read, Byte Array to String

Problem Statement

In this box stacking problem, we need to return the maximum possible height, which can be achieved by stacking the 3D boxing one above the other. In order to stack the box one above the other, we need to keep the following points into consideration,

  • The dimensions of the base of the box, which is meant to be placed at another box, should be strictly less than that of the dimensions of the box on which we are going to place the box.
  • We can rotate the box if we want to satisfy the first condition.

You can refer to this link to practice this problem.

Sample Example

Input: { (50, 45, 20); (95, 37, 53); (45, 23, 12) }

Output: 190

Explanation : 

In this case, we have three boxes of the given dimensions as input. The box with base dimensions of 53 * 37 along with the height of 95 is placed on the bottom. The box with base dimensions of 45 * 20 along with the height of 50 is placed on the box with base 53 * 37, and now the box with base dimensions of 12 * 23 along with the height of 45 is placed above the box that has base dimensions of 45 * 20. 

Approach - 1

Brute Force Solution considers generating all the three possible rotations of the boxes and storing them in an array that will be thrice the size of the number of boxes. Then we need to sort this array in decreasing order of the base area. Now we need to calculate the result at the ith stage by taking the maximum of the height of that ith box and the result of the stages before i. The final answer will be the maximum value of results of each stage already stored in the array.

Steps of Algorithm

Step 1. Create a function ‘getResult()’ that will accept two parameters, i.e., one array naming arr1 and the size of the array ‘N’.

Step 2. Create a class ‘box’ with height, depth, width as its members.

Step 3. Initialize an array of objects ‘temp’ of ‘box’ class of thrice the size of ‘N’. 

Step 4. Make an iteration using the ‘for’ loop, and store the dimensions with respect to each rotation in the ‘temp’ .

Step 5. Change the value of ‘N’ to ‘3 * N’. 

Step 6. Make another iteration using the ‘for’ loop, to store the height of each object ‘temp’ in an array of integers ‘msh’. 

Step 7. To get the optimized MSH, we need to use the nested ‘for’ loop using ‘i’ and ‘j’ variable, and in this, if width and depth of object at ith index are less than the width and depth of object at jth index and if the value at the ith index of ‘msh’ is less than the sum of the value at the jth index of ‘MSH’ and height of the object at the ith index of ‘temp’, then assign the sum of the value at the jth index of ‘MSH’ and height of the object at the ith index of ‘temp’ to ith index of ‘MSH’.

Step 8. Make another iteration using the ‘for’ loop to get the maximum value of ‘msh’ and return that value. 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Box class used to define the height, weight, depth of the box
class Box
{
  public:
  int h, w, d;
};

// To get a minimum of two numbers
int min (int x, int y)
{ 
  return (x < y)? x : y;
}

// To get a maximum of two numbers
int max (int x, int y)
{
  return (x > y)? x : y;
}

// Comparator function
int compare (const void *a, const void * b)
{
  return ((*(Box *)b).d * (*(Box *)b).w) - ((*(Box *)a).d * (*(Box *)a).w );
}

// To get result
int getResult(Box arr[], int n )
{

  // 'Temp' array to store the dimensions of all three rotations
  Box temp[3 * n];
  int index = 0;
  for (int i = 0; i < n; i++)
  {
      // Copy the original box
      temp[index].h = arr[i].h;
      temp[index].d = max(arr[i].d, arr[i].w);
      temp[index].w = min(arr[i].d, arr[i].w);
      index++;

      // First rotation of box
      temp[index].h = arr[i].w;
      temp[index].d = max(arr[i].h, arr[i].d);
      temp[index].w = min(arr[i].h, arr[i].d);
      index++;

      // Second rotation of box
      temp[index].h = arr[i].d;
      temp[index].d = max(arr[i].h, arr[i].w);
      temp[index].w = min(arr[i].h, arr[i].w);
      index++;
  }

  // change the size to thrice the size of the box
  n = 3 * n;

  // Sort the array
  qsort (temp, n, sizeof(temp[0]), compare);

  // Array to store all the results at each stage/ level
  int msh[n];
  for (int i = 0; i < n; i++ )
  {
      msh[i] = temp[i].h;
  }
  // Optimized MSH
  for (int i = 1; i < n; i++ )
  {
      for (int j = 0; j < i; j++ )
      {
          if ( temp[i].w < temp[j].w && temp[i].d < temp[j].d && msh[i] < msh[j] + temp[i].h)
          {
              msh[i] = msh[j] + temp[i].h;
          }
      }
  }

  // Maximum value of MSH
  int max = -1;
  for ( int i = 0; i < n; i++ )
  {
      if ( max < msh[i] )
      {
          max = msh[i];
      }
  }
  return max;
}
/* Driver program to test above function */
int main()
{
  Box arr[] = { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} };
  int n = sizeof(arr)/sizeof(arr[0]);
  cout << "Total Number of Boxes: " << n << endl;
  cout << "Dimensions of each Box: " << endl;
  for(int i = 0 ; i < n  ; i++)
  {
      cout << arr[i].w << " * " << arr[i].h << " * " << arr[i].d << endl;
  }

  cout << "The Maximum possible Height of the Stack is: ";
  cout << getResult(arr, n) << endl;
  return 0;
}

 

Output:

Total Number of Boxes: 4
Dimensions of each Box: 
6 * 4 * 7
2 * 1 * 3
5 * 4 * 6
12 * 10 * 32
The Maximum possible Height of the Stack is: 60

 

Complexity Analysis

Time Complexity: O(N ^ 2)

Incall to ‘getResult()’, we are using a nested loop in getting the optimized MSH(maximum stack height), therefore, the overall time complexity is O(N ^ 2).

Space Complexity: O(N)

As we are using space of size ‘N’ - the total number of boxes, therefore, the overall space complexity will be O(N).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach - 2

As we can shuffle any dimension of the box by rotating it to stack it on another box, so we should sort the dimensions of the boxes. After sorting, we can see that the condition of 

width[i] <= width[j] and length[i] <= length[j] and height[i] <= height[j]

So now, we applied a method to compare each pair of the box with the help of loop, if the condition is satisfied, then we can position the box ‘I’ on box ‘J’. 

Steps of Algorithm 

Step 1. In the function call ‘getResult()’, it will receive one parameter only: one 2D vector ‘input’. 

Step 2. We need to sort the boxes and their dimensions using the inbuilt sort function.

Step 3. Create an integral vector ‘dp’ of size ‘N’, where ‘N’ is the total number of boxes and an integral variable ‘result’, which will be used to store the result and initialize it with zero.

Step 4.  Make a nested iteration using the ‘for’ loop with variables ‘I’ and ‘j’, and check for the mandatory condition mentioned above.

Step 5. If the condition is validated true, then store the maximum of the value at ‘ith’ index of ‘dp’ and the sum of the value at ‘jth’ index of ‘dp’ along with input[i][2] at ‘ith’ index of ‘dp’.

Step 6. Update the value of ‘result’ with the maximum value amongst ‘result’ and the value at the ‘ith’ index of ‘dp’.

Step 7. Return the value of ‘result’. 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
int getResult(vector<vector<int>> &input)
{
   for(auto& x:input)
   {
       sort(begin(x), end(x));
   }
   input.push_back({0, 0, 0});
   sort(begin(input), end(input));

   int n = input.size();
   int result = 0;
   vector<int> dp(n);
   for(int i = 1 ; i < n ; i++)
   {
       for(int j = 0; j < i ; j++)
       {
           if(input[j][0] <= input[i][0] && input[j][1] <= input[i][1] && input[j][2] <= input[i][2])
           {
               dp[i] = max(dp[i], dp[j] + input[i][2]);
               result = max(result, dp[i]);
           }
       }
   }
   return result;
}
int main()
{
   vector<vector<int>> input = { {20, 45, 50}, {37, 53, 95}, {45, 23, 12}};
   cout << "Total Number of Boxes: " << input.size() << endl;
   cout << "Dimensions of each Box: " << endl;
   for(int i = 0 ; i < input.size() ; i++)
   {
       for(int j = 0 ; j < 2 ; j++)
       {
           cout << input[i][j] << " * ";
       }
       cout << input[i][2] << endl;
   }

   cout << "The Maximum possible Height of the Stack is: " << getResult(input) << endl;
}

 

Output:

Total Number of Boxes: 3
Dimensions of each Box: 
20 * 45 * 50
37 * 53 * 95
45 * 23 * 12
The Maximum possib

 

Complexity Analysis

Time Complexity: O(N^ 2)

In call to ‘getResult’ function, we are sorting the complete vector containing the dimensions of boxes using the inbuilt ‘sort’ function, which takes ‘N * LogN’ computational time, and then we are iterating for all the ‘N’ number of boxes using the nested ‘for’ loop which takes N * N computational time in the worst case, where ‘N’ is the total number of boxes. Therefore, the overall time complexity is O(N ^ 2).

Space Complexity: O(N)

As we are using an extra space of size ‘N’ to store the calculations in the ‘dp’ vector, where ‘N’ is the total number of boxes. Therefore, the overall space complexity is O(N).

FAQs

  1. What is the ‘sort’ inbuilt function in C++?
    ‘Sort’ is an inbuilt function in C++ that is used to sort the container which has been passed in the function. The average case time complexity of the inbuilt sort function is O(N * Log N).
     
  2. What is the difference between the arguments when we need to sort the array or the vector using the inbuilt ‘sort’ function?
    In the case of arrays, we just need to pass the name of the array, and the other argument is the name of the array with addition to the size of the array, whereas, in the case of vectors, we need to pass the initial pointer of the vector and the ending iterator of the vector.
     
  3. Why are we only considering the longest edge as the height?
    If we have the answer that has at least one box with the longest edge, not as height, then we can just rotate it without affecting adjacent boxes and make the total height of the stack larger.

Key Takeaways

In this article, we discussed the box stacking problem, discussed the various approaches to solving this problem programmatically, and the time and space complexities. 

Recommended Problem - K Closest Points To Origin

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.
Until then, All the best for your future endeavors, and Keep Coding.

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass