box stacking - Naukri Code 360

Q: 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).

Q: 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.

Q: 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.

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.

In this blog, we will explore the Box Stacking problem, learning about its core concepts, different approaches, and how to implement it in various programming languages.

To Read, Byte Array to String

What is box stacking problem?

The box stacking problem is a classic algorithmic challenge often used to illustrate dynamic programming concepts. The problem involves stacking a set of boxes to achieve the maximum possible height. Each box has dimensions (length, width, and height), and you can rotate the boxes to use any of these dimensions as the height. The challenge is to stack the boxes such that no box rests on a smaller box in both length and width.

To solve the problem, you first generate all possible rotations of the boxes. Then, you sort the boxes based on the base area (length × width) in descending order. After sorting, you apply dynamic programming to determine the maximum stack height at each box, considering it as the topmost box in the stack. The final solution is the maximum value obtained from these calculations.

This problem helps in understanding how to optimize solutions by breaking down complex problems into smaller sub-problems and combining their solutions effectively.

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

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

C++
Java
Python
JavaScript
C#

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;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.Arrays;

class Box {
    int height, width, depth;

    Box(int h, int w, int d) {
        height = h;
        width = w;
        depth = d;
    }
}

public class BoxStacking {
    public static int getResult(Box[] boxes) {
        int N = boxes.length;
        Box[] temp = new Box[3 * N];
        int index = 0;

        // Generate all rotations of each box
        for (Box box : boxes) {
            temp[index++] = new Box(box.height, Math.max(box.depth, box.width), Math.min(box.depth, box.width));
            temp[index++] = new Box(box.width, Math.max(box.height, box.depth), Math.min(box.height, box.depth));
            temp[index++] = new Box(box.depth, Math.max(box.height, box.width), Math.min(box.height, box.width));
        }

        // Sort boxes by base area (width * depth)
        Arrays.sort(temp, (a, b) -> (b.width * b.depth) - (a.width * a.depth));

        // Initialize MSH array
        int[] msh = new int[3 * N];
        for (int i = 0; i < 3 * N; i++) {
            msh[i] = temp[i].height;
        }

        // Compute MSH
        for (int i = 1; i < 3 * N; i++) {
            for (int j = 0; j < i; j++) {
                if (temp[i].width < temp[j].width && temp[i].depth < temp[j].depth && msh[i] < msh[j] + temp[i].height) {
                    msh[i] = msh[j] + temp[i].height;
                }
            }
        }

        // Return maximum height
        int maxHeight = 0;
        for (int height : msh) {
            maxHeight = Math.max(maxHeight, height);
        }

        return maxHeight;
    }

    public static void main(String[] args) {
        Box[] boxes = {
            new Box(4, 6, 7),
            new Box(1, 2, 3),
            new Box(4, 5, 6),
            new Box(10, 12, 32)
        };

        System.out.println("Total Number of Boxes: " + boxes.length);
        System.out.println("Dimensions of each Box:");
        for (Box box : boxes) {
            System.out.println(box.width + " * " + box.height + " * " + box.depth);
        }

        System.out.println("The Maximum possible Height of the Stack is: " + getResult(boxes));
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class Box:
    def __init__(self, height, width, depth):
        self.height = height
        self.width = width
        self.depth = depth

def getResult(boxes):
    N = len(boxes)
    temp = []
    
    # Generate all rotations of each box
    for box in boxes:
        temp.append(Box(box.height, max(box.depth, box.width), min(box.depth, box.width)))
        temp.append(Box(box.width, max(box.height, box.depth), min(box.height, box.depth)))
        temp.append(Box(box.depth, max(box.height, box.width), min(box.height, box.width)))
    
    # Sort boxes by base area (width * depth)
    temp.sort(key=lambda b: b.width * b.depth, reverse=True)
    
    # Initialize MSH array
    msh = [0] * len(temp)
    for i in range(len(temp)):
        msh[i] = temp[i].height
    
    # Compute MSH
    for i in range(1, len(temp)):
        for j in range(i):
            if (temp[i].width < temp[j].width and temp[i].depth < temp[j].depth and 
                msh[i] < msh[j] + temp[i].height):
                msh[i] = msh[j] + temp[i].height
    
    # Return maximum height
    return max(msh)

# Test the implementation
boxes = [
    Box(4, 6, 7),
    Box(1, 2, 3),
    Box(4, 5, 6),
    Box(10, 12, 32)
]

print("Total Number of Boxes:", len

You can also try this code with Online Python Compiler

Run Code

JavaScript

class Box {
    constructor(height, width, depth) {
        this.height = height;
        this.width = width;
        this.depth = depth;
    }
}

function getResult(boxes) {
    const N = boxes.length;
    const temp = new Array(3 * N);
    let index = 0;

    // Generate all rotations of each box
    boxes.forEach(box => {
        temp[index++] = new Box(box.height, Math.max(box.depth, box.width), Math.min(box.depth, box.width));
        temp[index++] = new Box(box.width, Math.max(box.height, box.depth), Math.min(box.height, box.depth));
        temp[index++] = new Box(box.depth, Math.max(box.height, box.width), Math.min(box.height, box.width));
    });

    // Sort boxes by base area (width * depth)
    temp.sort((a, b) => (b.width * b.depth) - (a.width * a.depth));

    // Initialize MSH array
    const msh = new Array(3 * N);
    for (let i = 0; i < 3 * N; i++) {
        msh[i] = temp[i].height;
    }

    // Compute MSH
    for (let i = 1; i < 3 * N; i++) {
        for (let j = 0; j < i; j++) {
            if (temp[i].width < temp[j].width && temp[i].depth < temp[j].depth && msh[i] < msh[j] + temp[i].height) {
                msh[i] = msh[j] + temp[i].height;
            }
        }
    }

    // Return maximum height
    return Math.max(...msh);
}

// Test the implementation
const boxes = [
    new Box(4, 6, 7),
    new Box(1, 2, 3),
    new Box(4, 5, 6),
    new Box(10, 12, 32)
];

console.log("Total Number of Boxes: " + boxes.length);
console.log("Dimensions of each Box:");
boxes.forEach(box => {
    console.log(box.width + " * " + box.height + " * " + box.depth);
});

console.log("The Maximum possible Height of the Stack is: " + getResult(boxes));

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;
using System.Linq;

public class Box
{
    public int Height { get; set; }
    public int Width { get; set; }
    public int Depth { get; set; }
}

public class BoxStacking
{
    public static int GetResult(Box[] boxes)
    {
        int N = boxes.Length;
        Box[] temp = new Box[3 * N];
        int index = 0;

        // Generate all rotations of each box
        foreach (var box in boxes)
        {
            temp[index++] = new Box { Height = box.Height, Width = Math.Max(box.Depth, box.Width), Depth = Math.Min(box.Depth, box.Width) };
            temp[index++] = new Box { Height = box.Width, Width = Math.Max(box.Height, box.Depth), Depth = Math.Min(box.Height, box.Depth) };
            temp[index++] = new Box { Height = box.Depth, Width = Math.Max(box.Height, box.Width), Depth = Math.Min(box.Height, box.Width) };
        }

        // Sort boxes by base area (width * depth)
        Array.Sort(temp, (a, b) => (b.Width * b.Depth).CompareTo(a.Width * a.Depth));

        // Initialize MSH array
        int[] msh = new int[3 * N];
        for (int i = 0; i < 3 * N; i++)
        {
            msh[i] = temp[i].Height;
        }

        // Compute MSH
        for (int i = 1; i < 3 * N; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (temp[i].Width < temp[j].Width && temp[i].Depth < temp[j].Depth && msh[i] < msh[j] + temp[i].Height)
                {
                    msh[i] = msh[j] + temp[i].Height;
                }
            }
        }

        // Return maximum height
        return msh.Max();
    }

    public static void Main()
    {
        Box[] boxes = {
            new Box { Height = 4, Width = 6, Depth = 7 },
            new Box { Height = 1, Width = 2, Depth = 3 },
            new Box { Height = 4, Width = 5, Depth = 6 },
            new Box { Height = 10, Width = 12, Depth = 32 }
        };

        Console.WriteLine("Total Number of Boxes: " + boxes.Length);
        Console.WriteLine("Dimensions of each Box:");
        foreach (var box in boxes)
        {
            Console.WriteLine(box.Width + " * " + box.Height + " * " + box.Depth);
        }

        Console.WriteLine("The Maximum possible Height of the Stack is: " + GetResult(boxes));
    }
}

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

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

C++
Java
JavaScript
C#
Python

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;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class BoxStacking {
    public static int getResult(List<List<Integer>> input) {
        for (List<Integer> box : input) {
            Collections.sort(box);
        }
        
        input.add(new ArrayList<>(List.of(0, 0, 0)));
        input.sort(Comparator.comparingInt(a -> a.get(2)));

        int n = input.size();
        int result = 0;
        int[] dp = new int[n];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (input.get(j).get(0) <= input.get(i).get(0) && input.get(j).get(1) <= input.get(i).get(1) && input.get(j).get(2) <= input.get(i).get(2)) {
                    dp[i] = Math.max(dp[i], dp[j] + input.get(i).get(2));
                    result = Math.max(result, dp[i]);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        List<List<Integer>> input = new ArrayList<>();
        input.add(new ArrayList<>(List.of(20, 45, 50)));
        input.add(new ArrayList<>(List.of(37, 53, 95)));
        input.add(new ArrayList<>(List.of(45, 23, 12)));

        System.out.println("Total Number of Boxes: " + input.size());
        System.out.println("Dimensions of each Box:");
        for (List<Integer> box : input) {
            System.out.println(box.get(0) + " * " + box.get(1) + " * " + box.get(2));
        }

        System.out.println("The Maximum possible Height of the Stack is: " + getResult(input));
    }
}

You can also try this code with Online Java Compiler

Run Code

JavaScript

function getResult(input) {
    input.forEach(box => box.sort((a, b) => a - b));

    input.push([0, 0, 0]);
    input.sort((a, b) => a[2] - b[2]);

    let n = input.length;
    let dp = new Array(n).fill(0);
    let result = 0;

    for (let i = 1; i < n; i++) {
        for (let 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] = Math.max(dp[i], dp[j] + input[i][2]);
                result = Math.max(result, dp[i]);
            }
        }
    }

    return result;
}

// Test the implementation
const input = [
    [20, 45, 50],
    [37, 53, 95],
    [45, 23, 12]
];

console.log("Total Number of Boxes: " + input.length);
console.log("Dimensions of each Box:");
input.forEach(box => {
    console.log(box.join(' * '));
});

console.log("The Maximum possible Height of the Stack is: " + getResult(input));

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;
using System.Collections.Generic;
using System.Linq;

public class BoxStacking
{
    public static int GetResult(List<List<int>> input)
    {
        foreach (var box in input)
        {
            box.Sort();
        }

        input.Add(new List<int> { 0, 0, 0 });
        input = input.OrderBy(box => box[2]).ToList();

        int n = input.Count;
        int result = 0;
        int[] dp = new int[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] = Math.Max(dp[i], dp[j] + input[i][2]);
                    result = Math.Max(result, dp[i]);
                }
            }
        }

        return result;
    }

    public static void Main()
    {
        var input = new List<List<int>>
        {
            new List<int> { 20, 45, 50 },
            new List<int> { 37, 53, 95 },
            new List<int> { 45, 23, 12 }
        };

        Console.WriteLine("Total Number of Boxes: " + input.Count);
        Console.WriteLine("Dimensions of each Box:");
        foreach (var box in input)
        {
            Console.WriteLine($"{box[0]} * {box[1]} * {box[2]}");
        }

        Console.WriteLine("The Maximum possible Height of the Stack is: " + GetResult(input));
    }
}

Python

def getResult(input):
    for box in input:
        box.sort()

    input.append([0, 0, 0])
    input.sort(key=lambda x: x[2])

    n = len(input)
    dp = [0] * n
    result = 0

    for i in range(1, n):
        for j in range(i):
            if (input[j][0] <= input[i][0] and input[j][1] <= input[i][1] and input[j][2] <= input[i][2]):
                dp[i] = max(dp[i], dp[j] + input[i][2])
                result = max(result, dp[i])

    return result

# Test the implementation
input = [
    [20, 45, 50],
    [37, 53, 95],
    [45, 23, 12]
]

print("Total Number of Boxes:", len(input))
print("Dimensions of each Box:")
for box in input:
    print(' * '.join(map(str, box)))

print("The Maximum possible Height of the Stack is:", getResult(input))

You can also try this code with Online Python Compiler

Run Code

Output

Total Number of Boxes: 3
Dimensions of each Box: 
20 * 45 * 50
37 * 53 * 95
45 * 23 * 12
The Maximum possible Height of the Stack is: 190

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

Frequently Asked Questions

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

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.

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.

Conclusion

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

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.