## 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).