Simple DP solution


  • 28
    L
    public int maxEnvelopes(int[][] envelopes) {
        if (   envelopes           == null
            || envelopes.length    == 0
            || envelopes[0]        == null
            || envelopes[0].length == 0){
            return 0;    
        }
        
        Arrays.sort(envelopes, new Comparator<int[]>(){
            @Override
            public int compare(int[] e1, int[] e2){
                return Integer.compare(e1[0], e2[0]);
            }
        });
        
        int   n  = envelopes.length;
        int[] dp = new int[n];
        
        int ret = 0;
        for (int i = 0; i < n; i++){
            dp[i] = 1;
            
            for (int j = 0; j < i; j++){
                if (   envelopes[i][0] > envelopes[j][0]
                    && envelopes[i][1] > envelopes[j][1]){
                    dp[i] = Math.max(dp[i], 1 + dp[j]);    
                }
            }
            
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

  • 0
    D

    Amazing code! I have a question. In comparator I tried to

    return e1[0] - e2[0];

    It gave me out of memory error. Could you please explain what's the different of these two operation? I thought they are same.


  • 0
    S

    May be overflow.
    Integer. MAX - Integer. MIN


  • 1
    B

    It did for me once as well. I re-ran and the issue went away without changing any code.


  • 0
    H

    what is the time complexity for this solution?


  • 0
    B

    The runtime is O(n^2). The outer loop goes through all indices and the inner loop goes all the way up to the outer loop. So worst case is n^2.


  • 0
    R

    @dasahcc
    You should use something like this:
    '''
    Arrays.sort(a, new Comparator<int[]>() {
    public int compare(int a1[], int a2[]) {
    return a1[0] * a1[1] - a2[0] * a2[1];
    }
    });
    '''


  • 0
    L

    @raj29

    I would never do something like a1[0] * a1[1] - a2[0] * a2[1] in a Comparator, that is going to expose us to an unexpected result due to Integer overflow


  • 0
    C

    @bdwalker definitely O(n^2). this solution is actually quite intuitive....


  • 1

    I got the same thing, perhaps a little more verbose but I find it readable. BTW, this is an easier version of the box-stacking problem:

    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null) return 0;
        if (envelopes.length <= 1) return envelopes.length;
        int max = 1, n = envelopes.length;      
        Arrays.sort(envelopes, (x, y) -> Integer.compare(y[0]*y[1], x[0]*x[1])); // sort by area
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
            int[] inner = envelopes[i];
            for(int j = 0; j < i; j++) {
                int[] outer = envelopes[j];
                if (outer[0] > inner[0] && outer[1] > inner[1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }       
        return max;
    }
    

  • 0

    I came up with the same solution in the first round. Considering it is O(n^2) time complexity while consuming O(n) space, it is not good enough to be a "hire" solution....


  • 0
    M

    A nitpit: in the comparator function, there is no need for @Override.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.