## Russian doll envelopes

There are a number of envelopes with widths and heights given as a pair of integers (w, h). An envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. Given the list of such envelope dimensions, find the maximum number of envelopes can you Russian doll? (put one inside other) For example:

```Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
```

How should we go about the solution? One of the ways is to find all the subsets of the envelopes and check every subset if envelopes can fit in each other. This solution has exponential time complexity. Can we do better than that?

Let’s look at the conditions again, an envelope can fit in another one only if width and height are smaller than the other envelope. Let’s simplify this. An envelope cannot fit into another one if the width is bigger than the other. What if we sort the envelopes based on their width? Then we are sure that i-th envelop can have all the envelopes inside it that are at index 0 to i-1 as far as the height permits.

Once, we order the envelopes based on width, our problem reduces to one dimension, which is height. Now if we want to find how many will fit in each other till envelope i, we find the envelopes from 0 to i-1 in increasing order. Why? Because even if the height of the envelope j is greater than height of envelope k, where k > j, it will not fit because width of envelope j is less than width of envelope k because of the sorted order.

To find the maximum number, all we have to is to find the longest increasing subsequence based on the height of envelopes.

One thing which you should take care of is what if the width of the two envelopes is the same? In that case, those two will not fit in together in each other even if heights are increasing. To handle this case, if widths are equal, we will put the envelope with a bigger height in front of the other, so that both envelopes are not part of increasing subsequence.

### Show me the implementation

```class Solution {
public int maxEnvelopes(int[][] envelopes) {

if(envelopes == null || envelopes.length == 0) return 0;

/*Sort the array based on width in increasing order,
if the width is equal, sort it based on height
in decreasing order.
*/
Arrays.sort(envelopes, (a,b) -> a == b
? b - a : a - b);

int n = envelopes.length;

int [] dp = new int[n];
int len = 0;

for(int[] envelope : envelopes){
int index = Arrays.binarySearch(dp, 0, len, envelope);

if(index < 0)
index = -(index + 1);
dp[index] = envelope;
if(index == len)
len++;
}

return len;
}
}
```

The time complexity of implementation is O(nlogn); we are doing n times binary search on maximum n numbers and space complexity is O(n).

You can solve another problem with the same approach: Box stacking problem, where one box can be put on another one only if the area of the base is less than the area of the base of another.

## 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, there are no active lists of subsequences, we will create a new one. Next, we go to A which is 8. A[i] is greater than the ends of all the current lists, we will take the longest one and append A to it. For A 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 . Clone it and append A to it and discard all other lists of the same length. For A with value 12, it is the same case as A 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 with value 2, it has the same case as A, Clone the one with largest end which is less than A, append A to it and discard all same length lists. A with value 10. Same as A. Clone, extend, and discard all the same length subsequences.
Lists = [ , [0, 2], [0,2,10] ] and [0, 4, 12] is discarded.

A is 6. Same as A We will clone the list which has end smaller than A, extend it, and discard all other lists which have the same length.
Lists = [ , [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. 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.