Russian doll envelopes

Tags: ,

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[0] == b[0] 
                           ? b[1] - a[1] : a[0] - b[0]);
        
        int n = envelopes.length;
        
        int [] dp = new int[n];
        int len = 0;
        
        for(int[] envelope : envelopes){
            int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
  
            if(index < 0)
                index = -(index + 1);
            dp[index] = envelope[1];
            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.