Box stacking problem 

Consider, we have been given 3-Dimensional boxes. Each box has width, depth and height (wi, di, hi). Box stacking problem is to stack these boxes in such a way that we achieve maximum height. There is one condition that is attached to it: A box can be placed on top of another only if both it’s base dimensions width and depth are less than a box on which it stacked on. There is no restriction on height, a tall box can be placed on a short box.
box stacking problem

With conditions in place, with given n boxes, we are actually, we are building a pyramid of boxes with maximum height.

This problem is closely related to longest increasing subsequence.

Recurrence relation for box stacking problem

Solution involves understanding of rotation aspects of the boxes. To avoid this aspect affect our solution, we list down all rotations of boxes as individual boxes. Therefore, for each box there are three representations. For example, for a box with dimensions a,b,c such that a>b>c

representation 1 : h=a, w=b, d=c>; 
representation 2 : h=b, w=a, d=c; 
representation 3 : h=c, w=a, d=b

Without losing generalization, we can avoid representation where wi < di. Now that we have three representations for each box, our input space increases to 3XN and the solution will be using these 3N boxes. There is another catch here. This solution works only when there are multiple instances of each box and we can use two different orientations of the same box while fetching maximum height.

Finding the sort order

Another problem is these boxes which are given to us are not ordered in any form. However, to stack boxes, we need to consider them in some order. As height does not affect stacking order, we can ignore it. Now, we have to consider only two dimensions.

Let’s say, we order boxes on the base area in decreasing order. How does it work? Consider two boxes with different base areas. It is impossible for a box with a larger base area to be stacked on top of a box with a smaller base area. There are only two dimensions, so at least one must be larger than the corresponding dimension smaller base area box. Therefore, if a box within our sequence can’t be placed on top, no box with a greater area can be placed on top either.

Let H(i) be the height of the stack of boxes 1,2,3,4…i. Modeling recurrent relation for H(i), put box i on a box j such that wi < wj and di < dj and H(j) is maximum for all j less than i.

H(i) = max(H(i), H(j) for all j < i such that wi < wj && di < dj ) + hi

Finally, output will be the maximum of all H[i].

Show me dynamic programming implementation

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct box {
    int width;
    int depth;
    int height;
} Box;

bool boxComparator(Box b1, Box b2) {
    return ( b1.depth * b1.width > b2.depth * b2.width );
}
 
int findMaxHeightBoxStack(Box boxes[], int n)
{
    int H[n];
    for(int i=0; i<n; i++){
        H[i] = boxes[i].height;
    }
    for(int i=1; i<n; i++){
    	for( int j=i-1; j>=0; j--){
    		if(boxes[j].width > boxes[i].width 
    		   && boxes[j].depth > boxes[i].depth 
    		   && H[j] + boxes[i].height){
    		   	H[i] = H[j] + boxes[i].height;
    		}
    	}
    }
	
	int maxHeight = 0 ;
	for(int i=0; i<n; i++){
		if(maxHeight < H[i]){
			maxHeight = H[i];
		}
	}
	return maxHeight;
}

int boxStacking(Box boxes[], int n)
{
	
	Box orientations[3*n]; //for rotations
	int index = 0;
	for(int i=0; i<n; i++){
		orientations[index] = boxes[i]; // first one as such
		index++;
		
		orientations[index].height = boxes[i].width;
		orientations[index].width = max( boxes[i].height, boxes[i].depth) ;
		orientations[index].depth = min( boxes[i].height, boxes[i].depth);
		
		index++;
		orientations[index].height = boxes[i].depth;
		orientations[index].width = max( boxes[i].height, boxes[i].width) ;
		orientations[index].depth = min( boxes[i].height, boxes[i].width) ;
		index++;
	}
	n = 3*n;

    sort(orientations, orientations+n, boxComparator);
	return findMaxHeightBoxStack( orientations, n);
}
 
// Driver program
int main()
{
    Box boxes[] = { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} };
    int n = sizeof(boxes)/sizeof(boxes[0]);
    cout << "Maximum height is " << boxStacking(boxes, n);
    return 0;
}

Implementation is quite simple, we need one dimension array H[]. These boxes are already sorted by area in decreasing order.

The complexity of the algorithm to find maximum height is O(n2) and space complexity is O(n).

This problem can be extended by putting boxes with K dimensions instead of 3 dimensions. Then also, the approach would be the same only number of orientations will change.

Please share if there is something is wrong or missing. If you want to contribute to algorithms and me, please contact us, we would love to hear from you.

Reference: https://people.cs.clemson.edu/~bcdean/dp_practice/dp_5.swf

Longest Increasing Subsequence in O(nlogn)

In the last post, longest increasing subsequence, we discussed brute force and dynamic programming based solutions. The complexity of the brute force solution is exponential whereas for the dynamic programming approach it is O(n2). Question is – Can we find the longest increasing subsequence in O(nlogn) complexity?

Let’s revisit the problem statement: Given an array of integers, find the length of the longest increasing subsequence. An increasing subsequence contains elements A[i] and A[j] only if i < j and A[i]A[j].
For example,

Input:
[2,4,5,3,1,6,7], 
Output:
5
Explanation:
The increasing subsequences are [2,4,5,6,7], [2,3,6,7], [1,6,7] and many more. The longest subsequence here has a length of 5.

The basic idea behind the solution is to keep track of all active subsequences at a given point in time. Based on the current number being considered, update these active lists. To understand this process, let’s work out an example.

A = {2,8,7}
Monotonically increasing subsequences are {2,8} and {2,7}

What if we add another element, 11 in this?

A = {2,8,7,11}
Monotonically increasing subsequences are {2,8,11} and {2,7,11}

What if new element 9 is added to array? What happens now? If we add it t0 subsequences, the length of the longest subsequence remains 3.

A = {2,8,7,11,9}
Monotonically increasing subsequences are {2,8,9} and {2,7,9}

The decision to take for each element being considered is whether we create new active subsequences with length 3 with element 9 in them or continue with 11. If the next element is 10 we know that adding 9 to subsequence leads us to longer subsequences rather than keeping 11.

How do we decide when to replace and when to continue with the old element in the list of subsequences?
We add a new number A[i] to the sequence if A[i] > E, E is the last element in subsequence
and replace an number with A[i], if there exists a number A[j] such that if E > A[i] < A[j], it means, the new number falls somewhere between A[j] and E.

What if A[i] is smaller than all elements in the present list of subsequences? In this case, we have to create a new list and add A[i] into it. The invariant is to maintain lists of increasing sequences and update them based on the next number.
Each time a new element is to be added, scan all the lists of subsequences in decreasing order of their length. The following algorithm shows how to add/replace the new elements in the existing lists or to create a new list with it.

1. If A[i] is the smallest among all end candidates of active lists, start a new active list with A[i] of length 1.
2. If A[i] is largest among all end candidates of active lists, clone the largest active list, and append A[i] to it.
3. If A[i] is in between, find the list with the largest end number that is smaller than A[i]. Clone and append A[i] to this list.
4. Discard all other lists of the same length as that of this modified list.

LIS in nlogn example

Let’s take an example and see how it works with an array A = [ 0, 8, 4, 12, 2, 10, 6, 14].

For A[0], there are no active lists of subsequences, we will create a new one.
longest increasing subsequence in logn

Next, we go to A[1] which is 8. A[i] is greater than the ends of all the current lists, we will take the longest one and append A[1] to it.
longest increasing subsequence in logn

For A[2] with value 4, A[i] is less than the end of one of the list and greater than the end of other. We will find the list which has end less than A[i], in this case, the first list containing [0]. Clone it and append A[2] to it and discard all other lists of the same length.

For A[3] with value 12, it is the same case as A[1] since it is greater than all the ends of the current lists, we will clone the longest available list and append it to that.

A[4] with value 2, it has the same case as A[2], Clone the one with largest end which is less than A[4], append A[4] to it and discard all same length lists.

A[5] with value 10. Same as A[4]. Clone, extend, and discard all the same length subsequences.
Lists = [ [0], [0, 2], [0,2,10] ] and [0, 4, 12] is discarded.

A[6] is 6. Same as A[5] We will clone the list which has end smaller than A[6], extend it, and discard all other lists which have the same length.
Lists = [ [0], [0, 2], [0,2,6] ] and [0, 2, 10] is discarded.

Following the same approach, we will go through all the numbers in the given array. The longest increasing subsequence in the given array is [ 0,2,6,14] with a length of 4.
lis in nlogn

It seems like a lot of things need to be done just for maintaining the lists and there is significant space complexity required to store all of these lists. We can optimize on this, observe that we use only ends of the list and their sizes. We do not care what was prior to them in list. So, can we store the ends of all the lists of an auxiliary array and do operations on them? Size of this array in worst case will be n.

To append to the list, add another element in the auxiliary array. To replace just overwrite the smallest number which is greater than the current number. To find the smallest number which is greater than the current number, we can use binary search algorithm.

To find the length of the longest subsequence, keep track of the length of the auxiliary array because this will be the length of LIS.

Show me implementation of longest increasing subsequence in O(nlogn)

    public int lengthOfLIS(int[] nums) {
        
        if(nums == null || nums.length == 0) return 0;
        
        int [] dp = new int[nums.length]; 
        int len = 0;
        
        for(int num : nums){
            int index = Arrays.binarySearch(dp, 0, len, num);
            
            if(index < 0)
                index = -(index+1);
            dp[index] = num;
            
            if(index == len)
                len++;
        }
        
        return len;
    }

The complexity of this algorithm is O(nlogn) as for each element in the array, it requires O(logn) time to find the ceiling of it and put it at the correct position.

This article has taken some inspiration from: http://stackoverflow.com/questions/6129682/longest-increasing-subsequenceonlogn and the comments provided by readers under these articles.

What are the problems you can solve with the longest increasing subsequence?
1. Russian doll envelopes.
2. Box stacking problem.
3. Bridges across the river.

Please share if you find something wrong or missing. Also, if you want to contribute to the website, please refer to Publishing and contact us. We would love to publish your article and at the same time, will pay you too.

Longest increasing subsequence

Given an array of integers, find the longest increasing subsequence i.e a subsequence such that every element of subsequence satisfy this condition: i < j  and a[i] < a[j].

Input: 
[3, 10, 2, 1, 20 ]
Output: 
3
Explanation:
The longest increasing subsequence is 3, 10, 20

Input:
[ 3, 2 ]
Output: 
1
Explanation:
The longest increasing subsequences are {3} and {2}

Input: 
[ 50, 3, 10, 7, 40, 80 ]
Output:
4
Explanation:
The longest increasing subsequence is {3, 7, 40, 80}

Longest common subsequence : thought process

If we have to find the longest increasing subsequence till the last element of an array, i.e nth element, the question is does that depend on LIS till n-1 elements before it? Idea is to see if any increasing subsequence already present till current index i,  can include  A[i] and still remain increasing? To confirm that, check every element at index j such that j>=0 and j < i and A[j] < A[i].

If A[j] is less than A[i], then A[i] can be part of increasing subsequence ending with element j. The length of such increasing subsequence can be (length of increasing subsequence ending at j )+1. Check for each such element and take maximum length. Let’s see an example and see how it works.

Before we start a solution, let’s think why are we applying dynamic programming here. First because, the solution to a bigger problem depends on the optimal solution of subproblems and second, because if we do not store solutions to subproblems we may end up calculating them again and again. Both Optimal subproblem property and overlapping subproblem property are satisfied with this problem and hence we will use dynamic programming to solve it.

LIS[i] will represent the longest increasing subsequence length till element i .

LIS[i] = 1 + max(LIS[j]) for all  0<=j<i and A[j]<A[i] 
       = 1 if no such element exists where j< i and A[j]<A[i]

Click here to see the implementation

class Solution {
    public int lengthOfLIS(int[] nums) {
        
        if(nums == null || nums.length == 0) return 0;
        
        int [] LIS = new int[nums.length];
        
        Arrays.fill(LIS, 1);
        
        int max = 1;
        
        for(int i=0; i<nums.length; i++){
            for(int j=i-1; j>=0; j--){
                if(nums[j] < nums[i] ){
                    LIS[i] = Math.max(LIS[i], LIS[j] + 1);
                }
            }
            max = Math.max(LIS[i], max);
        }
        return max;
    }
}

Let’s take an example and see how this code works? For example, given array A = {2,4,6,3,5,7,9}

Initialize LIS[0] =1, that means there is an increasing subsequence of length 1 at index 0.
For i = 1 i.e 4, check for j=0 to 1, excluding index 1. A[0] < A[1], hence LIS length is 2 (LIS[0] + 1 ).

For i = 2, i.e. 6 , check j = 0 to 2.  and check that LIS[0] = 1 and LIS[1] =2. Max LIS[j] for j=0 to  2 is 2. LIS[2] = 3 (LIS[1] +1).
For i =3 i.e 3, check from 0 to 3, Max LIS till index 3 will be LIS[3] = 2 because only A[0] is less than A[3]. Hence longest subsequence ending with i = 3 will have length only of 2.  LIS[3] = 2
For i = 4, i.e.5 Max LIS is again 3 which includes {2,4,5} or {2,3,5}
For i = 5, i.e 7, Max LIS is 4 which includes {2,4,5,7} or {2,3,5,7} or {2,4,6,7}
For i = 6, i.e 9, Max LIS is 5 which includes {2,4,5,7,9} or {2,3,5,7,9} or {2,4,6,7,9}

Therefore, the longest increasing subsequence is 6 for a given array.

Other problems which are a variance of longest increasing subsequence and can be solved by finding the longest increasing subsequence are :

1. Given two river banks (visualization: two parallel lines), one bank has numbers written (1….n) in sorted order. On the other bank, the numbers (1…n) are arranged randomly. A bridge can be formed from the ith point from bank 1 to ith point in bank 2. Find the max number of non-intersecting bridges you can form?
Just find the longest increasing subsequence in unordered number and that will be the solution.

2. Given a set of n types of rectangular 3-D boxes, where the ith box has height h(i), width w(i), and depth d(i) (all real numbers). You want to create a stack of boxes that are as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box.

3. Another problem which borrow heavily from approach is find longest zigzag subsequence in an array

Algorithm to find longest increasing subsequence works in O(n2) in time complexity with O(n) space complexity.

Please share if you find anything wrong or missing, we would love to hear from you. If you want to be part of editors and contributors team at Algorithms and Me, please drop us an email at [email protected]