354. Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One 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.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Note: Rotation is not allowed.

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

Solution

Recrursive + memorization : O(NlogN + N)

    int[][] envelopes;
    int[] dp;
    int n = 0;
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (e1, e2)->{
           if(e1[0] != e2[0]){
               return Integer.compare(e1[0], e2[0]);
           }
           return Integer.compare(e1[1], e2[1]);
        });
        this.envelopes = envelopes;
        this.n = envelopes.length;
        dp = new int[n];
        Arrays.fill(dp, -1);
        
        return helper(0, -1);
    }
    
    public int helper(int index, int prev){
        int count = 0; 
        if(index >= n) return count;
        if(prev != -1 && dp[prev] != -1) return dp[prev];  
        for(int i = index; i < n; i++){
            if(prev == -1 || ((envelopes[i][0] > envelopes[prev][0]) && (envelopes[i][1] > envelopes[prev][1]))){
                count = Math.max(helper(i+1, i) + 1, count);
            }
        }
        if(prev == -1) return count;
        return dp[prev] = count;
    }

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        
        //Sort the envelopes based on the width to reduce it to 
        //300. Longest increasing subsequence 
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] arr1, int[] arr2){
                if(arr1[0] == arr2[0])
                    return arr2[1] - arr1[1];
                else
                    return arr1[0] - arr2[0];
            } 
        });
        
        //check the longest increasing subsequnce base on height of evelope
        //since the evelopes is sorted by width i.e envelope[i][0] > envelope[i-1][0]
        //so if the envelope[i][1] > envelope[i-1][1], 
        //it means envelope[i] can contains envelope[i-1], reduced it to LC. 300. 
        int[] minEnvelopes = new int[envelopes.length];
        int len = 0;
        for(int[] envelope : envelopes){
            int i = Arrays.binarySearch(minEnvelopes, 0, len, envelope[1]);
            if(i < 0) i = -(i+1);
            minEnvelopes[i] = envelope[1];
            if(len == i) len++;
            
        }
        return len;    
    }
    
}